邻接表：
邻接矩阵： 空间复杂度：邻接表比邻接矩阵少了接近1/4的大小。
难点：图的构建、拓扑排序、计算值、逻辑运算
数字电路抽象出来就是有向图，中间的过程是模拟作为边的入度的点使用位计算其值作为该点的权值，最后输入的结果就是类似于计算点权重。 步骤：
1 构建图（邻接表、邻接矩阵），【构建的时候，就计算每个点的入度】；2 存储需要测试的输入、输出数据；3 使用拓扑排序来判断是否电路（有向图）是否成环；4 使用类似与拓扑排序的方法来从前向后依次计算每个元器件（点）的值。注意点：
每次计算下一个问题时，需要重新初始化变量；每次计算时，存储原始的入度，使用临时的入度来计算（因为计算时会多次用到入度）；使用std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree));复制数组时，ccf的编译器会爆编译错误；计算与非（NAND）和异或时（NOR）时，非操作只最后进行一次；注意换行、空格的输出；下文中，输入的点的编号用0～m-1来表示，元器见点的编号用m～m+n-1来表示以下图为例，抽象为一个有向图： 抽象后的结果：
邻接表：
#include<cstdio> #include<vector> #include<string> #include<iostream> #include<queue> #include<string.h> #include<algorithm> //#include <bits/stdc++.h> //using namespace std; const int MAXV = 510; typedef struct Node{ int v;//边的终点 Node(int _v):v(_v){}//初始化列表 }node; std::vector<node> Adj[MAXV];//邻接表 //int G[MAXV][MAXV] = {0};//邻接矩阵 int w[MAXV];//边权重 //bool inq[MAXV] = {false};//是否访问过 bool initV[MAXV] = {false};//是否初始化过边 int inDegree[MAXV] = {0};//入度 //int outDegree[MAXV] = {0};//出度（未使用） std::string type[MAXV]; //器件类型 std::vector<int> testInput[10010];//测试输入 std::vector<int> testOutput[10010];//测试输出 //拓扑排序，判断环 bool TopologicalSort(int n, int m){ int num = 0; std::queue<int> q; int tempInDegree[MAXV];//临时存储入度 memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数 // std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree)); for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队 if(tempInDegree[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front(); q.pop(); //邻接表 for(int i = 0;i < Adj[u].size();i++){ int v = Adj[u][i].v; tempInDegree[v]--; if(tempInDegree[v] == 0){ q.push(v); } } //邻接矩阵 // for(int i = 0; i < m + n;i++){ // if(inq[i] == false && G[u][i] != 0){ // tempInDegree[i]--; // // if(tempInDegree[i] == 0){ // q.push(i); // inq[i] = true; // } // } // } num++; } if(num == n + m) return true; else return false; } //计算值 void calculateValue(int n, int m){ std::queue<int> q; int tempInDegree[MAXV];//临时存储入度 memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数 for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队 if(tempInDegree[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front();//起始点 q.pop(); //邻接表 for(int i = 0;i < Adj[u].size();i++){ int v = Adj[u][i].v; tempInDegree[v]--; if(initV[v] == false){//之前没有被访问过 w[v] = w[u];//赋予初始值 if(type[v] == "NOT"){//最多或者最少都只有一个输入 w[v] = (!w[v]); } initV[v] = true; }else{ if(type[v] == "AND" || type[v] == "NAND"){ w[v] &= w[u]; }else if(type[v] == "OR" || type[v] == "NOR"){ w[v] |= w[u]; }else if(type[v] == "XOR"){ w[v] ^= w[u]; } } if(tempInDegree[v] == 0){ if(type[v] == "NAND" || type[v] == "NOR"){ w[v] = (!w[v]); } q.push(v); } } // for(int i = 0; i < m + n;i++){ // if(inq[i] == false && G[u][i] != 0){ // tempInDegree[i]--; // // if(initV[i] == false){//之前没有被访问过 // w[i] = w[u];//赋予初始值 // if(type[i] == "NOT"){//最多或者最少都只有一个输入 // w[i] = (!w[i]); // } // initV[i] = true; // }else{ // if(type[i] == "AND" || type[i] == "NAND"){ // w[i] &= w[u]; // }else if(type[i] == "OR" || type[i] == "NOR"){ // w[i] |= w[u]; // }else if(type[i] == "XOR"){ // w[i] ^= w[u]; // } // } // // if(tempInDegree[i] == 0){//入度为零，以它为终点的边数为0 // if(type[i] == "NAND" || type[i] == "NOR"){ // w[i] = (!w[i]); // } // q.push(i); // inq[i] = true; // } // } // } } } int main(){ int q, m, n; scanf("%d", &q); while(q--){//问题个数 //初始化 for(int i = 0;i < MAXV;i++){ for(std::vector<node>::iterator j = Adj[i].begin();j != Adj[i].end();){ j = Adj[i].erase(j); } } //std::fill(G[0], G[0] + MAXV*MAXV, 0); memset(inDegree, 0, sizeof(inDegree)); //memset(outDegree, 0, sizeof(outDegree)); // std::fill(inq, inq + MAXV, false); std::fill(initV, initV + MAXV, false); for(int i = 0;i < MAXV;i++){ type[i].clear(); } for(int i = 0;i < 10010;i++){ for(std::vector<int>::iterator j = testInput[i].begin();j != testInput[i].end();){ j = testInput[i].erase(j); } } for(int i = 0;i < 10010;i++){ for(std::vector<int>::iterator j = testOutput[i].begin();j != testOutput[i].end();){ j = testOutput[i].erase(j); } } scanf("%d%d", &m, &n);//输入个数，器件个数 for(int num = m;num < n + m;num++){ std::string FUNC;//器件描述 int k; std::cin>>FUNC; type[num] = FUNC; scanf("%d", &k); for(int i = 0;i < k;i++){ std::string L; std::cin>>L; int startPoint = std::atoi(L.substr(1, L.length() - 1).c_str()) - 1;//计算起始点编号 if(L[0] != 'I'){//如果是输出点，则加上输入点的偏移 startPoint += m; } Adj[startPoint].push_back(node(num));//构造图 //G[startPoint][num] = 1; // outDegree[startPoint]++;//计算出度 inDegree[num]++;//计算入度 } } int s;//运算次数 scanf("%d", &s); for(int i = 0;i < s;i++){//输入数据 for(int j = 0;j < m;j++){ int input; scanf("%d", &input); testInput[i].push_back(input); } } for(int i = 0;i < s;i++){//输出数据 int OutNum; scanf("%d", &OutNum); while(OutNum--){ int output; scanf("%d", &output); output = output + m - 1; testOutput[i].push_back(output); } } if(TopologicalSort(n, m) == false){//有环 printf("LOOP\n"); }else{//无环 for(int i = 0;i < s;i++){ memset(w, 0, sizeof(w)); //std::fill(inq, inq + MAXV, false); std::fill(initV, initV + MAXV, false); for(int j = 0;j < testInput[i].size();j++){//给初始输入点赋值 w[j] = testInput[i][j]; } //计算点权 calculateValue(n, m); for(int j = 0; j < testOutput[i].size();j++){ if(j != 0) printf(" "); printf("%d", w[testOutput[i][j]]); } printf("\n"); } } }//q return 0; } 邻接矩阵 #include<cstdio> #include<vector> #include<string> #include<iostream> #include<queue> #include<string.h> #include<algorithm> //#include <bits/stdc++.h> //using namespace std; //typedef struct Node{ // int v;//边的终点 // Node(int _v):v(_v){}//初始化列表 //}node; //std::vector<node> Adj[510];//邻接表 const int MAXV = 510; int G[MAXV][MAXV] = {0};//邻接矩阵 int w[MAXV];//边权重 bool inq[MAXV] = {false};//是否访问过 bool initV[MAXV] = {false};//是否初始化过边 int inDegree[MAXV] = {0};//入度 int outDegree[MAXV] = {0};//出度（未使用） std::string type[MAXV]; //器件类型 std::vector<int> testInput[10010];//测试输入 std::vector<int> testOutput[10010];//测试输出 //拓扑排序，判断环 bool TopologicalSort(int n, int m){ int num = 0; std::queue<int> q; int tempInDegree[MAXV];//临时存储入度 memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数 // std::copy(std::begin(inDegree), std::end(inDegree), std::begin(tempInDegree)); for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队 if(tempInDegree[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front(); q.pop(); // for(int i = 0;i < Adj[u].size();i++){ // int v = Adj[u][i].v; // inDegree[v]--; // if(inDegree[v] == 0){ // q.push(v); // } // } for(int i = 0; i < m + n;i++){ if(inq[i] == false && G[u][i] != 0){ tempInDegree[i]--; if(tempInDegree[i] == 0){ q.push(i); inq[i] = true; } } } num++; } if(num == n + m) return true; else return false; } //计算值 void calculateValue(int n, int m){ std::queue<int> q; int tempInDegree[MAXV];//临时存储入度 memcpy(tempInDegree, inDegree, (m+n)* sizeof(int));//复制的字节数 for(int i = 0;i < n + m;i++){//将所有入度为0的顶点入队 if(tempInDegree[i] == 0){ q.push(i); } } while(!q.empty()){ int u = q.front();//起始点 q.pop(); for(int i = 0; i < m + n;i++){ if(inq[i] == false && G[u][i] != 0){ tempInDegree[i]--; if(initV[i] == false){//之前没有被访问过 w[i] = w[u];//赋予初始值 if(type[i] == "NOT"){//最多或者最少都只有一个输入 w[i] = (!w[i]); } initV[i] = true; }else{ if(type[i] == "AND" || type[i] == "NAND"){ w[i] &= w[u]; }else if(type[i] == "OR" || type[i] == "NOR"){ w[i] |= w[u]; }else if(type[i] == "XOR"){ w[i] ^= w[u]; } } if(tempInDegree[i] == 0){//入度为零，以它为终点的边数为0 if(type[i] == "NAND" || type[i] == "NOR"){ w[i] = (!w[i]); } q.push(i); inq[i] = true; } } } } } int main(){ int q, m, n; scanf("%d", &q); while(q--){//问题个数 //初始化 std::fill(G[0], G[0] + MAXV*MAXV, 0); memset(inDegree, 0, sizeof(inDegree)); memset(outDegree, 0, sizeof(outDegree)); std::fill(inq, inq + MAXV, false); std::fill(initV, initV + MAXV, false); for(int i = 0;i < MAXV;i++){ type[i].clear(); } for(int i = 0;i < 10010;i++){ for(std::vector<int>::iterator j = testInput[i].begin();j != testInput[i].end();){ j = testInput[i].erase(j); } } for(int i = 0;i < 10010;i++){ for(std::vector<int>::iterator j = testOutput[i].begin();j != testOutput[i].end();){ j = testOutput[i].erase(j); } } scanf("%d%d", &m, &n);//输入个数，器件个数 for(int num = m;num < n + m;num++){ std::string FUNC;//器件描述 int k; std::cin>>FUNC; type[num] = FUNC; scanf("%d", &k); for(int i = 0;i < k;i++){ std::string L; std::cin>>L; int startPoint = std::atoi(L.substr(1, L.length() - 1).c_str()) - 1;//计算起始点编号 if(L[0] != 'I'){//如果是输出点，则加上输入点的偏移 startPoint += m; } //Adj[startPoint].push_back(node(num));//构造图 G[startPoint][num] = 1; outDegree[startPoint]++;//计算出度 inDegree[num]++;//计算入度 } } int s; scanf("%d", &s); for(int i = 0;i < s;i++){//输入数据 for(int j = 0;j < m;j++){ int input; scanf("%d", &input); testInput[i].push_back(input); } } for(int i = 0;i < s;i++){//输出数据 int OutNum; scanf("%d", &OutNum); while(OutNum--){ int output; scanf("%d", &output); output = output + m - 1; testOutput[i].push_back(output); } } if(TopologicalSort(n, m) == false){ printf("LOOP\n"); }else{ for(int i = 0;i < s;i++){ memset(w, 0, sizeof(w)); std::fill(inq, inq + 510, false); std::fill(initV, initV + MAXV, false); for(int j = 0;j < testInput[i].size();j++){ w[j] = testInput[i][j]; } calculateValue(n, m); for(int j = 0; j < testOutput[i].size();j++){ if(j != 0) printf(" "); printf("%d", w[testOutput[i][j]]); } printf("\n"); } } }//q return 0; }输出：
1 0 1 0 1 1 0 0 2 输入： 1 2 6 NOR 2 O4 I2 AND 2 O4 O6 XOR 2 O5 O1 NOT 1 O6 NAND 2 O2 O2 AND 2 I1 O3 2 0 0 1 0 3 2 3 4 6 1 2 3 4 5 6输出：
LOOP 3 输入： 1 3 9 AND 3 I1 I2 I3 OR 3 I1 I2 I3 AND 2 I1 I2 AND 2 I1 I3 AND 2 I2 I3 OR 2 O1 O7 AND 2 O2 O8 NOT 1 O9 OR 3 O3 O4 O5 8 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9 2 6 9输出：
0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 4 1 3 8 NAND 2 O2 O3 NAND 2 I1 O4 NAND 2 I2 O4 NAND 2 I1 I2 NAND 2 O6 O7 NAND 2 O1 O8 NAND 2 I3 O8 NAND 2 O1 I3 8 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5输出：
0 1 1 0 1 0 0 1 5 输入： 1 1 2 AND 2 I1 O2 NOT 1 O1 2 0 1 0 0 2 1 2输出：
LOOP测试数据部分参考：https://blog.csdn.net/H_X_P_/article/details/108569908
