题意:问至少还需要加入多少条有向边才能变成强连通图.
答案=max(in0,out0),特判scc=1.
代码:
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #define min(a,b) (a<b?a:b) 5 #define max(a,b) (a>b?a:b) 6 using namespace std; 7 const int MAXE=2e5+7; 8 const int MAXV=2e4+7; 9 int V,E; 10 struct edge{ 11 int next,v; 12 }es[MAXE]; 13 int head[MAXV],tot; 14 void init(){ 15 tot=0; 16 memset(head,-1,sizeof(head)); 17 } 18 void addEdge(int u,int v){ 19 es[tot].v=v; 20 es[tot].next=head[u]; 21 head[u]=tot++; 22 } 23 int low[MAXV],dfn[MAXV],time; 24 int belong[MAXV],scc; 25 bool instack[MAXV]; 26 stack<int>s; 27 void dfs(int u,int pre){ 28 low[u]=dfn[u]=++time; 29 instack[u]=true; 30 s.push(u); 31 for(int i=head[u];~i;i=es[i].next){ 32 int v=es[i].v; 33 if(!dfn[v]){ 34 dfs(v,u); 35 low[u]=min(low[u],low[v]); 36 }else if(instack[v]){ 37 low[u]=min(low[u],dfn[v]); 38 } 39 } 40 if(low[u]==dfn[u]){ 41 scc++; 42 for(;;){ 43 int now=s.top();s.pop(); 44 belong[now]=scc; 45 instack[now]=false; 46 if(now==u)break; 47 } 48 } 49 } 50 int in[MAXV],out[MAXV]; 51 int main(){ 52 int T;scanf("%d",&T); 53 while(T--){ 54 scanf("%d%d",&V,&E); 55 init(); 56 memset(in,0,sizeof(in)); 57 memset(out,0,sizeof(out)); 58 memset(low,0,sizeof(low)); 59 memset(dfn,0,sizeof(dfn)); 60 memset(instack,0,sizeof(instack)); 61 memset(belong,0,sizeof(belong)); 62 time=scc=0; 63 for(int i=0;i<E;++i){ 64 int a,b;scanf("%d%d",&a,&b); 65 addEdge(a,b); 66 } 67 for(int i=1;i<=V;++i){ 68 if(!dfn[i]){ 69 dfs(i,-1); 70 } 71 } 72 // printf("scc=%d ",scc); 73 if(scc==1){ 74 printf("0 "); 75 continue; 76 } 77 for(int u=1;u<=V;++u){//缩点后的操作,对代表元进行操作 78 for(int i=head[u];~i;i=es[i].next){ 79 int v=es[i].v; 80 if(belong[u]!=belong[v]){ 81 out[belong[u]]++; 82 in[belong[v]]++; 83 } 84 } 85 } 86 int IN=0,OUT=0; 87 for(int i=1;i<=scc;++i){ 88 // printf("in[%d]=%d,out[%d]=%d ",i,in[i],i,out[i]); 89 if(in[i]==0)++IN; 90 if(out[i]==0)++OUT; 91 } 92 printf("%d ",max(IN,OUT)); 93 } 94 return 0; 95 }