意甲冠军：给定一个有向图有m单向边缘。免费推断是否两点起来（a可以b要么b可以a或最多彼此)，该请求

            弱联通重量。

算法：

缩点求强连通分量。然后又一次建图。推断新图是否是一条单链，即不能分叉，假设分叉了就会存在不可达的情况。

怎么推断是否是单链呢?

就是每次入度为0的点都仅仅有一个，即每次队列里仅仅有一个点。

（    o(╯□╰)o。。。。

。好像已经是第二次用pair记录原图的点对，然后存pair的vector忘记清空导致wa来wa去！

）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define maxn 1010#define maxm 20010using namespace std;struct node{    int to,next;}edge[maxm],edge2[maxm];int head[maxn],cnt,n;int clk,top,s[maxn],scc,dfn[maxn],low[maxn],belong[maxn];bool instack[maxn],vis[maxn];int head2[maxn],cnt2,in[maxn];typedef pair
          
            PII;vector
           
             xx;queue
            
              q;void add(int x,int y){ edge[cnt].to = y; edge[cnt].next = head[x]; head[x] = cnt++;}void add2(int x,int y){ edge2[cnt2].to = y; edge2[cnt2].next = head2[x]; head2[x] = cnt2++;}void dfs(int x){ dfn[x] = low[x] = clk++; s[top++] = x; instack[x] = true; for(int i=head[x];i!=-1;i = edge[i].next) { int u = edge[i].to; if(dfn[u]==-1) { dfs(u); low[x] = min(low[u],low[x]); } else if(instack[u]) { low[x] = min(low[x],dfn[u]); } } if(low[x]==dfn[x]) { int u; scc++; do { u = s[--top]; instack[u]=false; belong[u] = scc; }while(u!=x); }}void tarjan(){ memset(dfn,-1,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(belong,0,sizeof(belong)); clk = top = scc = 0; for(int i=1;i<=n;i++) { if(dfn[i]==-1) dfs(i); }}bool topo(){ memset(vis,0,sizeof(vis)); int c = 0; while(!q.empty()) q.pop(); for(int i=1;i<=scc;i++) { if(!in[i]) { c++; q.push(i); } } if(c>1) return false; while(!q.empty()) { int u = q.front(); q.pop(); if(vis[u]) continue; vis[u] = true; c = 0; for(int i=head2[u];i!=-1;i=edge2[i].next) { int v = edge2[i].to; in[v]--; if(!in[v]) { q.push(v); c++; } } if(c>1) return false; } return true;}int main(){ int m,a,b,T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); memset(in,0,sizeof(in)); xx.clear(); cnt = 0; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); xx.push_back(make_pair(a,b)); } tarjan(); memset(head2,-1,sizeof(head2)); cnt2 = 0; for(int i=0;i
            
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。