88分,来个大佬救场
查看原帖
88分,来个大佬救场
230808
Zxsoul楼主2020/10/21 21:42
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int manx = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

struct node{
	int u,v,nxt;           
}e[manx<<1];
node ee[manx<<1];
int zxs,head[manx],cnt,headd[manx],n,m,low[manx],lt[manx],dfn[manx],js,top,st[manx],cl[manx],zbc;
int id[manx],cd[manx];
int ans=1,sbw;
int add(int u,int v){
	e[++cnt].nxt = head[u];
	e[cnt].u = u;
	e[cnt].v = v;
	head[u] = cnt;
}


int tarjan(int u){
	low[u] = dfn[u] = ++js;
	st[++top] = u;
	for(int i = head[u];i;i = e[i].nxt ){
		int  v = e[i].v;  
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if(!lt[v]){
			low[u] = min(low[u],dfn[v]);
		}
	} 
	if(dfn[u] == low[u]){
		lt[u] = ++zxs;
		while(st[top] != u)lt[st[top--]] = zxs;
		top --;
	}
}
int addd(int u,int v){
	ee[++zbc].nxt = headd[u];
	ee[zbc].u = u;
	ee[zbc].v = v;
	headd[u] = zbc;
	}
int main(){
	n = read(),m = read();
	for(int i = 1;i <= m;i ++){
		int x = read(),y = read();
		add(x,y);
	}
	for(int i = 1;i <= n;i ++){
		if(dfn[i] == 0)
		tarjan(i);
	}
	for(int i = 1;i <= n; i++){
		for(int j = head[i];j;j = e[j].nxt )
		{ 
			int v = e[j].v; 
			if(lt[i] != lt[v])
			{
				addd(lt[i],lt[v]);
			}
		} 
	}
	for(int i = 1; i <= zxs; i++){
		for(int j = headd[i];j ;j = ee[j].nxt)
		{
			int v = ee[j].v ;
			cd[i]++;
			id[v]++;
		}
	}
	for(int i = 1;i <= zxs; i++)
	{
		if(cd[i] == 0)
		{
			for(int  j = 1;j <= n; j++){
				if(lt[j] == i)
				sbw++;
			} 
			break;
		}
	}
	cout<<sbw;
}
2020/10/21 21:42
加载中...