25pts求调,不知道哪出错了
查看原帖
25pts求调,不知道哪出错了
759274
Stevehim楼主2023/3/2 22:27
#include <bits/stdc++.h>
#define maxe 500050
#define maxv 100050
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]; //记录出度
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 >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		if (u == v)
			continue;
		G[u].push_back(v); //单向建边
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) { //选择没有的
			tarjan(i);
		}
	}
//	for (int i = 1; i <= n; i++) {
//		cout << belong[i] << endl;
//	}
//	cout << endl;
	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]]++; //出度增加,便于合并
			}
		}
	}
	int res = 0, ans;
	for (int i = 1; i <= tot; i++) {
		if (outdegree[i] == 0) {
			res++;
			ans = i;
		}
	}
	cout << res;
	return 0;
}

2023/3/2 22:27
加载中...