蒟蒻求助Tarjan,以关注作回报
  • 板块P2002 消息扩散
  • 楼主hc_awa
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/7/1 19:33
  • 上次更新2023/11/4 20:27:36
查看原帖
蒟蒻求助Tarjan,以关注作回报
366470
hc_awa楼主2021/7/1 19:33

第13个点WA

#include <set>
#include <stack>
#include <cstdio>
#include <vector>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e5+7,M=5e5+7;

vector<int> edge[N];
set<pair<int,int> > s;
stack<int> sta;

int x[M],y[M];
int dfn[N],low[N];
int leader[N];
bool vis[N],indeg[N];

int n,m,ans;
int deep;

void Tarjan(int u) {
	dfn[u]=low[u]=++deep;
	sta.push(u),vis[u]=true;
	for(int i=0,v;i<edge[u].size();++i) {
		v=edge[u][i];
		if(!dfn[v]) {
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])
			low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u])
		while(!sta.empty()) {
			int r=sta.top();
			sta.pop();
			leader[r]=u;
			vis[r]=false;
			if(u==r) 
				break;
		}
}

signed main() {
	int mm;
	scanf("%d%d",&n,&mm);
	for(int i=1;i<=mm;++i) {
		scanf("%d%d",x+i,y+i);
		if(x[i]!=y[i] && s.find({x[i],y[i]})==s.end()) {
			edge[x[i]].push_back(y[i]);
			++m;
			s.insert({x[i],y[i]});
		}
	}
	
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			Tarjan(i);
	
	for(int i=1;i<=m;++i)
		if(leader[x[i]]!=leader[y[i]])
			indeg[leader[y[i]]]=true;
	for(int i=1;i<=n;++i)
		if(!indeg[i] && leader[i]==i)
			++ans;
	printf("%d",ans);
    return 0;
}
2021/7/1 19:33
加载中...