Tarjan 不知道哪错了求调QAQ
查看原帖
Tarjan 不知道哪错了求调QAQ
759274
Stevehim楼主2023/6/24 22:40
#include <bits/stdc++.h>
#define maxe 50005
#define maxv 10005
using namespace std;
vector<int> G[maxe];
int n, m;
int cnts = 1;
int low[maxv]; //为根节点的子树最近访问
int dfn[maxv];
int belong[maxv];
int s[maxv];
int top = 0;
int cnt = 0, tot = 0;
int num[maxv]; //每个强连通分量点的个数
int outdegree[maxv]; //记录出度
int indegree[maxv]; //记录出度
bool vis[maxv];

void tarjan(int x) {
	int c;
	low[x] = dfn[x] = ++cnt; //记录初始的时间戳和最近访问
	s[++top] = x; //入栈
	vis[x] = true; //标记访问
	for (int u = 0; u < G[x].size(); u++) {
		c = G[x][u]; //好写一些
		if (!dfn[c]) { //没有访问
			tarjan(c); //递归下去
			low[x] = min(low[x], low[c]); //进行判定
		} else if (vis[c]) { //已经访问过了
			low[x] = min(low[x], dfn[c]);
		}
	}
	if (dfn[x] == low[x]) { //如果等于证实是一个强连通分量,因为压根没做改动
		tot++;
		c = -1;
		while (x != c) { //找出强连通分量
			c = s[top--]; //取出
			belong[c] = tot; //表上序号
			num[tot]++;
			vis[c] = false;
		}
	}
}

int main() {
	//	memset(head, -1, sizeof(head));
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int v;
		while(1){
			cin >> v;
			if(v == 0) break;
			else G[i].push_back(v);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) { //选择没有的
			tarjan(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int u = 0; u < G[i].size(); u++) {
			if (belong[G[i][u]] != belong[i]) {
				outdegree[belong[i]]++; //出度增加,便于合并
				indegree[belong[G[i][u]]]++;
			}
		}
	}
	int res = 0, res2 = 0;
	for (int i = 1; i <= tot; i++) {
		if (outdegree[i] == 0) {
			res++;
		}
		if(indegree[i] == 0){
			res2++;
		}
	}
	if(tot == 0) cout << 1 << endl << 0 << endl;
	else cout << res << endl << max(res,res2);
	return 0;
}
2023/6/24 22:40
加载中...