求联通分量个数，在dfs一次
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <stack> #include <cstdlib> #include <iomanip> #include <cmath> #include <cassert> #include <ctime> #include <map> #include <set> using namespace std; #pragma comment(linker, "/stck:1024000000,1024000000") #define lowbit(x) (x&(-x)) #define max(x,y) (x>=y?x:y) #define min(x,y) (x<=y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.1415926535897932384626433832 #define ios() ios::sync_with_stdio(true) #define INF 0x3f3f3f3f #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int n,m,cap,ans=0,cnt=0,top=-1,pos=0; int head[5006],low[5006],dnf[5006],Stack[5006],vis[5006]; vector<int>vv[5006],fv[5006]; int belong[5006],in[5006],u[5006],v[5006]; void tarjan(int u) { low[u]=dnf[u]=++cnt; Stack[++top]=u; vis[u]=1; int v; for(int i=0;i<fv[u].size();i++) { v=fv[u][i]; if(!dnf[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) low[u]=min(dnf[v],low[u]); } if(low[u]==dnf[u]) { ans++; do { v=Stack[top--]; belong[v]=ans; vis[v]=0; }while(u!=v); } } void solve() { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) if(!dnf[i]) tarjan(i); } void dfs(int u) { vis[u]=1; for(int i=0;i<vv[u].size();i++) if(!vis[vv[u][i]]) dfs(vv[u][i]); } int main() { scanf("%d%d%d",&n,&m,&cap); for(int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); fv[u[i]].push_back(v[i]); } solve(); memset(in,0,sizeof(in)); for(int i=1;i<=m;i++) { if(belong[u[i]]==belong[v[i]]) continue; vv[belong[u[i]]].push_back(belong[v[i]]); in[belong[v[i]]]++; } memset(vis,0,sizeof(vis)); dfs(belong[cap]); int inf=0; for(int i=1;i<=ans;i++) inf+=(!in[i] && !vis[i]); printf("%d ",inf); return 0; }