ccf csp 2020年09月 第三題：點亮數位人生（dfs + 判環）

題目背景
土豪大學的計算機系開了一門數位邏輯電路課，第一個實驗叫做「點亮數位人生」，要用最基礎的邏輯元件組裝出實際可用的電路。時間已經是深夜了，儘管實驗箱上密密麻麻的連線已經拆裝了好幾遍，小君同學卻依舊沒能讓她的電路正常工作。你能幫助她模擬出電路的功能，成功點亮她的數位人生嗎？

問題描述
本題中，你需要實現一個簡單的數位邏輯電路模擬器。如果你已經有了此方面的基礎，可以直接跳過本節。在閱讀時，也可以參照前兩個樣例的圖示和解釋，這有助於你更好地理解數位邏輯電路的工作原理。

數位邏輯電路是用來傳輸數位訊號（也就是二進位制訊號）的電路。一般來說，數位邏輯電路可以分為兩大類，即組合邏輯（combinational logic）電路和時序邏輯（sequential logic）電路。在本題中，我們僅關注組合邏輯電路。這種電路僅由邏輯閘（logical gate）構成。一個邏輯閘可以理解為一個多輸入單輸出的函數，輸入端連線至少一個訊號，而後經過一定的邏輯運算輸出一個訊號。常見的邏輯閘包括與（AND）、或（OR）、非（NOT）、互斥或（XOR）等，均與程式語言中的按位元運算是對應的。

將一系列的邏輯閘連線起來，就能構成具有特定功能的電路。它的功能可能很簡單（如一位二進位制加法只需要一個互斥或門），也可能極其複雜（如除法）。無論複雜程度，這類電路的特點是：它不維持任何的狀態，任何時刻輸出只與輸入有關，隨輸入變化。真實世界中的邏輯裝置由於物理規律的限制，存在訊號傳播延時。為了簡單起見，本題中我們模擬的組合邏輯電路不考慮延時：一旦輸入變化，輸出立刻跟著變化。

考慮到組合邏輯電路的這一特性，設計時不能允許組合環路（combinational loop）的存在，即某邏輯閘的輸入經過了一系列器件之後又被連線到了自己的輸入端。真實世界中，這種做法將導致電路變得不穩定，甚至損壞元器件。因此，你也需要探測可能的環路。需要注意，環路的存在性與邏輯閘的具體功能沒有任何關係；只要連線關係上存在環路，電路就無法正常工作。
感想：考試的時候讀電路輸入輸出的時候以為編號只有一位，然後讀入時唯讀了一個數位，實際上是可以有O10 ， I100這樣的讀入，讀的時候可以用字串流或者sscanf。
思路：先按照給出的電路圖存圖，然後dfs模擬即可，還有一個小坑是隻要圖有環，就算要輸出的部分不涉及環路也判LOOP（我最開始只判斷要輸出的部分，得了80分），判環可以用拓撲排序，或者直接dfs加標記即可

程式碼：
dfs + 拓撲排序判環

#include <bits/stdc++.h>


using namespace std;

const int maxn = 705 , N = 2e4 + 5;

struct gate{
	string func;
	vector <int> ii;
	vector <int> o;
	int out;
	gate() {
		out;
	}
	gate(string s) : func(s){}
};

int tin[N][maxn * 6] , tout[N] , mout[maxn] , in[N];
int vis[maxn];
vector <int> ans[N];
vector <gate> g;

bool dfs(int u , int k ) {
	//if(vis[u]) return false;
	if(mout[u] != -1)return mout[u];
	int res = 0;
	if(g[u].func[0] == 'X') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res ^= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res ^= mout[v];
		}
		mout[u] = res;
		//cout << "u = " << u << "res = " << res << endl;
	}
	else if(g[u].func[0] == 'A') {
		res = 1;
		bool flag = 0;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func[0] == 'O') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NOT") {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res = !tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res = !mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NAND") {
		res = 1;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = !res;
	}
	else {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = !res;
	}
	return true;
}

bool tp(int n ) {
	for(int i = 1 ; i <= n ; i++) {
		for(int j = 0; j < g[i].o.size() ; j++) {
			int v = g[i].o[j];
			in[v]++;
		}
	}
	queue <int> q;
	int cnt = 0;
	for(int i = 1 ; i <= n ; i++) {
		if(!in[i]) {
			cnt++;
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(in[v] == 1) {
				q.push(v);
				cnt++;
			}
			in[v]--;
		}
	}
	if(cnt < n)return false;
	else return true;
	
}


int main() {
	int Q;
	int m , n;
	ios::sync_with_stdio(0);
	cin >> Q;
	while(Q--) {
		cin >> m >> n;
		g.clear();
		g.push_back(gate());
		memset(in , 0 , sizeof(in));
		for(int i = 1 ; i <= n ; i++) {
			string func;
			int k;
			cin >> func >> k;
			gate g1 = gate(func);
			while(k--) {
				string s;
				cin >> s;
				int t = 0;
				stringstream ss(s.substr(1));
				ss >> t;
				if(s[0] == 'O')g1.o.push_back(t);
				else if(s[0] == 'I')g1.ii.push_back(t);
			}
			g.push_back(g1);
		}
		int s;
		cin >> s;
		for(int i = 1 ; i <= s ; i++) {
			for(int j = 1 ; j <= m ; j++) {
				cin >> tin[i][j];
			}
		}
		bool flag = 0;
		memset(vis , 0 , sizeof(vis));
		if( !tp(n) ) {
			flag = 1;
		}
		for(int i = 1 ; i <= s ; i++) {
			int si;
			for(int j = 1 ; j <= n ; j++)mout[j] = -1;
			cin >> si;
			for(int j = 1 ; j <= si ; j++) {
				cin >> tout[j];
			}
			
			for(int j = 1 ; j <= si && !flag; j++) {
				dfs(tout[j] , i);
				ans[i].push_back(mout[tout[j]]);
			}
		}
		if(!flag) {
			for(int i = 1 ; i <= s ; i++) {
				for(int j = 0 ; j < ans[i].size() ; j++) {
					if(j > 0)cout << " ";
					cout << ans[i][j];
				}
				cout << "\n";
			}
		}
		else {
			cout << "LOOP\n";
		}
		for(int i = 1 ; i <= s; i++) {
			ans[i].clear();
		}
	}
	return 0;
}

dfs + dfs判環：

#include <bits/stdc++.h>


using namespace std;

const int maxn = 705 , N = 2e4 + 5;

struct gate{
	string func;
	vector <int> ii;
	vector <int> o;
	int out;
	gate() {
		out;
	}
	gate(string s) : func(s){}
};

int tin[N][maxn * 6] , tout[N] , mout[maxn] , in[N];
int vis[maxn];
vector <int> ans[N];
vector <gate> g;

bool dfs(int u , int k ) {
	//if(vis[u]) return false;
	if(mout[u] != -1)return mout[u];
	int res = 0;
	if(g[u].func[0] == 'X') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res ^= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res ^= mout[v];
		}
		mout[u] = res;
		//cout << "u = " << u << "res = " << res << endl;
	}
	else if(g[u].func[0] == 'A') {
		res = 1;
		bool flag = 0;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func[0] == 'O') {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NOT") {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res = !tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res = !mout[v];
		}
		mout[u] = res;
	}
	else if(g[u].func == "NAND") {
		res = 1;
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res &= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res &= mout[v];
		}
		mout[u] = !res;
	}
	else {
		for(int i = 0 ; i < g[u].ii.size() ; i++) {
			int v = g[u].ii[i];
			res |= tin[k][v];
		}
		for(int i = 0 ; i < g[u].o.size() ; i++) {
			int v = g[u].o[i];
			if(mout[v] == -1 ) {
				if(!dfs(v , k));//return false;
			}
			res |= mout[v];
		}
		mout[u] = !res;
	}
	return true;
}

bool solve(int u , int f) {
	if(vis[u]) {
		if( vis[u] == f )return false;
		return true;
	}
	vis[u] = f;
	for(int i = 0 ; i < g[u].o.size() ; i++) {
		int v = g[u].o[i];
		if(!solve(v , f) ) {
			return false;
		}
	}
	
	return true;
}

bool tp(int n ) {
	
	for(int i = 1 ; i <= n ; i++) {
		if(!vis[i] && !solve(i , i)) {
			
			return false; 
		}
	}
	return true;
}


int main() {
	int Q;
	int m , n;
	ios::sync_with_stdio(0);
	cin >> Q;
	while(Q--) {
		cin >> m >> n;
		g.clear();
		g.push_back(gate());
		memset(in , 0 , sizeof(in));
		for(int i = 1 ; i <= n ; i++) {
			string func;
			int k;
			cin >> func >> k;
			gate g1 = gate(func);
			while(k--) {
				string s;
				cin >> s;
				int t = 0;
				stringstream ss(s.substr(1));
				ss >> t;
				if(s[0] == 'O')g1.o.push_back(t);
				else if(s[0] == 'I')g1.ii.push_back(t);
			}
			g.push_back(g1);
		}
		int s;
		cin >> s;
		for(int i = 1 ; i <= s ; i++) {
			for(int j = 1 ; j <= m ; j++) {
				cin >> tin[i][j];
			}
		}
		bool flag = 0;
		memset(vis , 0 , sizeof(vis));
		if( !tp(n) ) {
			flag = 1;
		}
		for(int i = 1 ; i <= s ; i++) {
			int si;
			for(int j = 1 ; j <= n ; j++)mout[j] = -1;
			cin >> si;
			for(int j = 1 ; j <= si ; j++) {
				cin >> tout[j];
			}
			
			for(int j = 1 ; j <= si && !flag; j++) {
				dfs(tout[j] , i);
				ans[i].push_back(mout[tout[j]]);
			}
		}
		if(!flag) {
			for(int i = 1 ; i <= s ; i++) {
				for(int j = 0 ; j < ans[i].size() ; j++) {
					if(j > 0)cout << " ";
					cout << ans[i][j];
				}
				cout << "\n";
			}
		}
		else {
			cout << "LOOP\n";
		}
		for(int i = 1 ; i <= s; i++) {
			ans[i].clear();
		}
	}
	return 0;
}