看不出来哪里错了QWQ
  • 板块P2835 刻录光盘
  • 楼主rish
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/17 14:26
  • 上次更新2024/9/17 14:32:31
查看原帖
看不出来哪里错了QWQ
257173
rish楼主2024/9/17 14:26
#include<bits/stdc++.h>
using namespace std;
const int N = 4e4+10;
struct Node{
	int to, next;
}g[N];
int n, x, cnt, tnt, num, h, a, ans;
int head[N], ori[N], co[N], low[N], q[N], in[N];
void Tarjan(int s)
{
	ori[s] = low[s] = ++num;
	q[++h] = s;
	for(int i=head[s];i;i=g[i].next)
	{
		if(!ori[g[i].to])
		{
			Tarjan(g[i].to);
			low[s] = min(low[g[i].to], low[s]);
		}
		else if(!co[g[i].to]) low[s] = min(low[s], ori[g[i].to]);
	}
	if(ori[s]==low[s])
	{
		co[s] = ++tnt;
		while(q[h]!=s) co[q[h--]] = tnt;
		h--;
	}
}
void add(int a, int b)
{
	g[++cnt].to = b;
	g[cnt].next = head[a];
	head[a] = cnt;
}
int main()
{
	int n, x;
	cin >> n;
	for(int i=1;i<=n;i++)
		while(cin >> x, x) add(i, x);
	for(int i=1;i<=n;i++) if(!ori[i]) Tarjan(i);
	for(int i=1;i<=n;i++) 
		for(int j=head[i];j;j=g[j].next) in[co[g[j].to]]++;
	for(int i=1;i<=tnt;i++) if(!in[i]) ans++;
	cout << ans << endl;
	return 0;
}

2024/9/17 14:26
加载中...