八十分,错俩点,新手刚学,求大佬指点
查看原帖
八十分,错俩点,新手刚学,求大佬指点
230808
Zxsoul楼主2020/10/21 18:02
#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];
int zxs,head[manx],cnt,n,m,low[manx],lt[manx],dfn[manx],js,top,st[manx],sbw[manx],cl;
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){
	
	dfn[u] = low[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);
			//cout<<u<<" "<<v<<" "<<low[u]<<" "<<low[v]<<endl;
			low[u] = min(low[u] ,low[v]);
			//cout<<u<<" "<<low[u]<<endl;
		}else if(!lt[v])
				low[u] = min(low[u], dfn[v]);
	}
	if(dfn[u] == low[u]){
		lt[u] = ++zxs;
		cl++;
		while(st[top] != u) 
		{
			lt[st[top--]] = zxs;
			sbw[cl]++;
		}
		top--;
	}
}

int ans;

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 <= cl; i++)
	{
		 if(sbw[i]>1)
			ans++;
	}
	cout<<ans;
}
2020/10/21 18:02
加载中...