有关T了3个点这码事
查看原帖
有关T了3个点这码事
371461
超能少年飞楼主2022/3/4 22:32

请问一下为什么会T掉#12,#20,#21 3个点? code:

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
	int next;
	int to;
} edge[10010];
int nxt[10010], max_edge = 0;
int dfn[10010], low[10010];
int id[10010], siz[10010];
int scc = 0, nows = 0;
bool in_stk[10010];
stack <int> stk;
int cd[10010];

void add_edge(int st, int to)
{
	edge[++max_edge].to = to;
	edge[max_edge].next = nxt[st];
	nxt[st] = max_edge;
}

void tarjan(int u)
{
	nows++;
	dfn[u] = low[u] = nows;
	stk.push(u);
	in_stk[u] = true;
	
	for (int i = nxt[u]; i != 0; i = edge[i].next)
	{
		if (dfn[edge[i].to] == 0)
		{
			tarjan(edge[i].to);
			low[u] = min(low[u], low[edge[i].to]);
		}
		else if (in_stk[edge[i].to])
		{
			low[u] = min(low[u], dfn[edge[i].to]);
		}
	}
	
	if (dfn[u] == low[u])
	{
		scc++;
		int tc; 
		do
		{
			tc = stk.top();
			stk.pop();
			in_stk[tc] = false;
			id[tc] = scc;
			siz[scc]++;
			//tc = stk.top();
		} while (u != tc);
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		add_edge(u, v);
	}
	
	for (int i = 1; i <= n; i++) if (dfn[i] == 0) tarjan(i);
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = nxt[i]; j != 0; j = edge[j].next)
		{
			int to = edge[j].to;
			if (id[i] != id[to])
			{
				cd[id[i]]++;
			}
			//cout << i << " " << to << endl;
		}
	}
	
	int flag = 0;
	for (int i = 1; i <= scc; i++)
	{
		if (cd[i] == 0)
		{
			if (flag != 0) 
			{
				cout << 0 << endl;
				return 0;
			}
			else flag = i;
		}
	}
	
	cout << siz[flag] << endl;
	return 0;
}
2022/3/4 22:32
加载中...