trajan WA 四点求救
查看原帖
trajan WA 四点求救
129390
yangwenbin楼主2020/8/2 15:25

trajan WA 17 18 19 20

#include <bits/stdc++.h>
using namespace std;
const int num = 10e4+50;
int n,m,ans,cnt,tot;
int dfn[num],low[num];
bool instack[num];
std::stack < int > stc;
std::vector< int > edge[num];
std::vector< int > belong[num];
void trajan(int u){
	dfn[u] = low[u] = ++tot;
	instack[u] = true;
	stc.push(u);
	int s = edge[u].size();
	for (int i = 0; i < s; ++i){
		int v = edge[u][i];
		if (!dfn[v]){
			trajan(v);
			low[u] = min(low[u],low[v]);
		}
		else if (instack[v]){
			low[u] = min(low[u],low[v]);
		}
	}
	if (dfn[u] == low[u]){
		int node;
		++cnt;
		do{
			node = stc.top();
			stc.pop();
			instack[node]=false;
			belong[cnt].push_back(node);
		} while (node != u);
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i){
		int x,y;
		scanf("%d %d",&x,&y);
		edge[x].push_back(y);
	}
	for(int i = 1; i <= n; ++i){
		if(!dfn[i]){
			trajan(i);
		}
	}
	for (int i = 1; i <= cnt; ++i){
		int s = belong[i].size();
		bool flat = true;
		for (int j = 0; j < s; ++j){
			int l = edge[belong[i][j]].size();
			for (int k = 0; k < l; ++k){
				if(low[belong[i][j]] == low[edge[belong[i][j]][k]]){
					continue;
				}
				else{
					flat = false;
					break;
				}
			}
			if (!flat){
				break;
			}
		}
		if (!flat){
			continue;
		}
		if(ans == 0){
			ans = s;
		}else{
			printf("0\n");
			return 0;
		}
	}
	printf("%d\n",ans);
}

为什么

2020/8/2 15:25
加载中...