72pts蒟蒻不懂问题所在(5555~
查看原帖
72pts蒟蒻不懂问题所在(5555~
393674
jixiang楼主2021/6/15 18:26
#include<bits/stdc++.h>
using namespace std;
const int M=100000;
vector<int>g[M];
//vector<int>new_g[M];
vector<int >col[M];
int c[M],dfn[M],low[M];
bool vis[M],in_stack[M];
int n,m,cnt,c_cnt;
stack<int>s;
int rudu[M];

void build()
{
	int f,t;
 	 cin>>n>>m;
 	 for(int i=1;i<=m;i++)scanf("%d%d",&f,&t),g[f].push_back(t);
} 


void tarjan(int x)
{
	int v;
	low[x]=dfn[x]=cnt++;
	s.push(x);
	vis[x]=in_stack[x]=true;
	for(int i=0;i<g[x].size();i++)
	{
		v=g[x][i];
		if(dfn[v]==0)
		{
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		
		else if(vis[v]&&in_stack[v])low[x]=min(low[x],dfn[v]);
	}
	
	
	if(low[x]==dfn[x])
	{
		c_cnt++;
	     while (s.top()!=x)
		{
			c[s.top()]=c_cnt;
			col[c_cnt].push_back(s.top());
			in_stack[s.top()]=false; 
			s.pop();
		}	
		    c[s.top()]=c_cnt;
			col[c_cnt].push_back(s.top());
			in_stack[s.top()]=false; 
			s.pop();
	}
	
}


void shape()
{
	int v;
	for(int i=1;i<=c_cnt;i++)
	{
		for(int k=0;k<col[i].size();k++)
		{
		    int u=col[i][k];
			for(int j=0;j<g[u].size();j++)
			{
				v=g[u][j];
		    	if(c[v]!=i)rudu[c[v]]++;
			}
		}
	}
}

int main()
{
	int ans;
	ans=0;
	build();
	for(int x=1;x<=n;x++)if(!dfn[x])tarjan(x);
	shape();
	for(int i=1;i<=c_cnt;i++)
		if(rudu[i]==c_cnt-1)ans+=col[i].size();
	cout<<ans;
	
 } 
2021/6/15 18:26
加载中...