2020-2021:teams:hotpot:tarjan

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:tarjan [2020/05/13 17:43]
misakatao 更新
+++ 2020-2021:teams:hotpot:tarjan [2020/05/13 20:25] (当前版本)
misakatao 更新
@@ 行 49: / 行 49: @@
 ====代码实现====
+<code cpp>
+#include <map>
+#include <set>
+#include <ctime>
+#include <cmath>
+#include <stack>
+#include <queue>
+#include <vector>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <algorithm>
+using namespace std;
+const int maxn = 10005;
+const int maxm = 50005;
+int n, m, tot, top, scc = 0, color[maxn], dfn[maxn], low[maxn], stk[maxn], d[maxn], siz[maxn], ins[maxn];
+int u[maxm], v[maxm], ans = 0;
+vector<int> g[maxn];
+inline void tarjan(int x)
+{
+	dfn[x] = low[x] = ++tot;
+	stk[++top] = x;
+	ins[x] = 1;
+	int s = g[x].size();
+	for(int i = 0;i < s;++i)
+	{
+		if(!dfn[g[x][i]])
+		{
+			tarjan(g[x][i]);
+			low[x] = min(low[x], low[g[x][i]]);
+		}
+		else
+			low[x] = min(low[x], dfn[g[x][i]]);//这里不是low[g[x][i]]是因为g[x][i]的low值可能还没更新过
+	}
+	if(dfn[x] == low[x])
+	{
+		int now = -1;
+		++scc;
+		while(now != x)
+		{
+			now = stk[top];
+			top--;
+			ins[now] = 0;
+			color[now] = scc;
+			++siz[scc];
+		}
+	}
+}
+int main()
+{
+	scanf("%d%d", &n, &m);
+	for(int i = 1;i <= m;++i)
+	{
+		scanf("%d%d", &u[i], &v[i]);
+		g[u[i]].push_back(v[i]);
+	}
+	for(int i = 1;i <= n;++i)
+		if(!dfn[i])
+			tarjan(i);
+	for(int i = 1;i <= m;++i)
+		if(color[u[i]] != color[v[i]])
+			++d[color[u[i]]];
+	for(int i = 1;i <= scc;++i)
+	{
+		if(!d[i])
+		{
+			if(ans > 0)
+			{
+				ans = 0;
+				break;
+			}
+			ans = siz[i];
+		}
+	}
+	printf("%d\n", ans);
+	return 0;
+}
+</code>

2020-2021/teams/hotpot/tarjan.1589363037.txt.gz · 最后更改: 2020/05/13 17:43 由 misakatao