tarjan求强连通分量-白红宇

tarjan求强连通分量

阅读量：4515 次

发布时间：2019-06-08

本文共 3356 字，大约阅读时间需要 11 分钟。

http://poj.org/problem?id=3180

//#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #define fi first#define se second#define INF 0x3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))#define lowbit(x) ((x)&(-x))const double pi=4.0*atan(1.0);const int maxn=1e5+8;typedef long long LL;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;using namespace std;struct node{ int to,nxt;}g[maxn*2];int head[maxn];int cnt=0;void add(int u,int v){ g[cnt].to=v; g[cnt].nxt=head[u]; head[u]=cnt++;}int deep=0;int dfn[maxn],low[maxn];bool vis[maxn];int Stack[maxn];int tail=0;int ans=0;void tarjan(int u){ dfn[u]=++deep; low[u]=deep; Stack[++tail]=u; vis[u]=1; int t=head[u]; int r=0; while(t!=-1){ if(!dfn[g[t].to]){ tarjan(g[t].to); low[u]=min(low[u],low[g[t].to]); } else{ if(vis[g[t].to]){ low[u]=min(low[u],low[g[t].to]); } } t=g[t].nxt; } if(dfn[u]==low[u]){ while(Stack[tail]!=u){ vis[Stack[tail]]=0; tail--; r=1; } vis[Stack[tail]]=0; tail--; } ans+=r;}int main(){ memset(head,-1,sizeof(head)); int n,m,x,y; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); add(x,y); } for(int i=1;i<=n;i++){ if(!dfn[i]){ tarjan(i); } } cout<
                 
                  <

无向图缩点

http://codeforces.com/group/w1oiqifZbS/contest/652/problem/E

#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))#define lowbit(x) ((x)&(-x))const double pi=4.0*atan(1.0);const int maxn=3e5+8;typedef long long LL;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;using namespace std;struct node{    int to,nxt;    bool val;}g[maxn*2],gg[maxn*2];int head[maxn],head2[maxn];int cnt=0;void add(int u,int v,bool val){    g[cnt].to=v;    g[cnt].nxt=head[u];    g[cnt].val=val;    head[u]=cnt++;}int deep=0;int dfn[maxn],low[maxn];bool vis[maxn];bool used[maxn];int Stack[maxn];bool a[maxn];int color[maxn];int tot=0;int tail=0;int n,m;void tarjan(int u,int fa){    dfn[u]=++deep;    low[u]=deep;    Stack[++tail]=u;    vis[u]=1;    int t=head[u];    while(t!=-1){        if(g[t].to==fa){            t=g[t].nxt;            continue;        }        if(!dfn[g[t].to]){            tarjan(g[t].to,u);            low[u]=min(low[u],low[g[t].to]);        }        else{            if(vis[g[t].to]){                low[u]=min(low[u],low[g[t].to]);            }        }        t=g[t].nxt;    }    if(dfn[u]==low[u]){        tot++;        while(Stack[tail]!=u){            vis[Stack[tail]]=0;            color[Stack[tail]]=tot;            tail--;        }        vis[Stack[tail]]=0;        color[Stack[tail]]=tot;        tail--;    }}void add2(int u,int v,int val){    gg[cnt].to=v;    gg[cnt].nxt=head2[u];    gg[cnt].val=val;    head2[u]=cnt++;}void suodian(){    for(int i=1;i<=n;i++){        int t=head[i];        while(t!=-1){            if(color[i]==color[g[t].to]){                a[color[i]]+=g[t].val;            }            else if(g[t].to>i){                //cout<
      <<' '<
       
        <

转载于:https://www.cnblogs.com/Profish/p/10421559.html

你可能感兴趣的文章

POJ 2311 Cutting Game(二维SG+Multi-Nim)

查看>>

小强的HTML5移动开发之路（16）——神奇的拖放功能

查看>>

zookeeper FastLeaderElection