ZOJ_3795 Grouping(強連通分量 拓撲)

ZOJ_3795 Grouping(強連通分量 拓撲)

題解：
這是我的第一道強連通分量，雖然參考了別人的代碼，還是很有收獲。強連通分量的查找和處理是很多圖論題目的第一步，所以還是很重要，這道題只是有向圖的強連通處理。
這道題因為題目有講每組關系都是不小於，那麼如果出現環的話那只有一種情況，就是環上所有人都是相等的年齡，則這個環上所有的人的比較關系都是可以等價的，這就是為什麼我們要先對強連通分量盡行縮點處理，將每一個強連通分量作為一個整體,之後再依據層次關系構造拓撲序，利用拓撲序找到最長的一條序列。
算法講解
代碼參考
測試數據：

4 4
1 2
2 3
3 4
4 1

5 3
1 2
2 3
3 4

9 9
5 4
4 1
1 3
3 2
2 1
1 6
6 7
7 8
8 9

5 5
1 2
2 3
3 4
4 1
5 1

代碼實現：

#include 
#include 
#include 
#include 
#include 
#include 
#define MAX_N 100010
#define MAX_M 300010

using namespace std;

struct E{
    int from,to,next;
    bool sign;
};
int N,M;
int result;
int edgenum;//邊的數目
int top,cnt,Time;//棧頂，強聯通分量數目，時間軸
E edge[MAX_M];//邊集
int dis[MAX_N];//拓撲序中節點的權值
int head[MAX_N];//前向星存儲head數組
int belong[MAX_N];//記錄某個點屬於哪一個強連通分量
int indegree[MAX_N];//記錄拓撲序中強連通分量入度
bool instack[MAX_N];//節點是否入棧
int DFN[MAX_N];//節點u搜索的次序編號（時間戳）
int Low[MAX_N];//節點u或u的子樹能追溯到的最早的棧中節點的次序號
int Stack[MAX_N];//手寫棧
vector G[MAX_N];//存儲拓撲序
vector bcnt[MAX_N];//存儲每一個強連通分量
void add(int u,int v);//前向星加邊
void tarjan(int u);//查找強連通分量
void tarjan_ini(int all);
void suodian();//縮點函數，按照每個強連通分量構造拓撲序
int bfs();

int main(){
    //freopen("in.txt","r",stdin);
    while( scanf("%d%d",&N,&M) != EOF ){
        int a,b;
        edgenum = 0;
        memset(head,-1,sizeof(head));
        while( M-- ){
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        tarjan_ini(N);
        suodian();
        result = bfs();
        printf("%d\n",result);
    }
    return 0;
}


void tarjan_ini(int all){
    memset(DFN,-1,sizeof(DFN));
    //初始化三個指針
    top = Time = cnt = 0;
    for( int i = 1; i <= all; i++ ){
        //查找每一個未被遍歷的點的強連通分量
        if( DFN[i] == -1 ){
            tarjan(i);
        }
    }
}

//遞歸查找強連通分量
void tarjan(int u){
    //標記時間戳
    DFN[u] = Low[u] = ++Time;
    //入棧，注意這裡的前++
    Stack[++top] = u;
    instack[u] = true;

    //查找所有與u相鄰邊，尋找強連通分量
    for( int i = head[u]; i != -1; i = edge[i].next ){
        E tmp = edge[i];
        //未被訪問節點
        if( DFN[tmp.to] == -1 ){
            tarjan(tmp.to);
            //u或u的子樹所能追溯到的最早的棧中節點
            Low[u] = min(Low[u],Low[tmp.to]);
        }
        //已被訪問且仍在棧中節點
        else if( instack[tmp.to] ){
            Low[u] = min(Low[u],DFN[tmp.to]);
        }
    }
    //u為強連通分量節點，彈棧，所有元素存儲到一個vector數組
    if( DFN[u] == Low[u] ){
        int now;
        cnt++;
        bcnt[cnt].clear();
        do{
            //彈棧，注意這裡的後--
            now = Stack[top--];
            //標記屬於哪一個強連通分量
            belong[now] = cnt;
            instack[now] = false;
            bcnt[cnt].push_back(now);
        }while( now != u );//彈到根節點截止
    }
}

void suodian(){
    for( int i = 1; i <= cnt; i++ ){
        G[i].clear();
        indegree[i] = 0;
    }
    //利用所有不在某一個強連通分量內部的邊構造拓撲序
    for( int i = 0; i < edgenum; i++ ){
        int u,v;
        u = belong[edge[i].from];
        v = belong[edge[i].to];
        if( u != v ){
            indegree[v]++;
            G[u].push_back(v);
        }
    }
}

void add(int u,int v){
    E tmp = {u,v,head[u],false};
    edge[edgenum] = tmp;
    head[u] = edgenum++;
}

int bfs(){
    int tmp;
    queue Q;
    for( int i = 1; i <= cnt; i++ ){
        if( indegree[i] == 0 ){
            Q.push(i);
            //初始權值為強連通分量的size
            dis[i] = bcnt[i].size();
        }
        else{
            dis[i] = 0;
        }
    }
    while( !Q.empty() ){
        int u = Q.front();
        Q.pop();
        int len = G[u].size();
        for( int i = 0; i < len; i++ ){
            int v = G[u][i];
            //疊加找到最大權值
            dis[v] = max(dis[v],(int)bcnt[v].size()+dis[u]);
            //若該圖為一個強連通圖，不會進入這裡更新
            //tmp = max(tmp,dis[v]);
            indegree[v]--;
            if( indegree[v] == 0 ){
                Q.push(v);
            }
        }
    }
    //得到結果
    tmp = 1;
    for( int i = 1; i <= cnt; i++ ){
        tmp = max(tmp,dis[i]);
    }
    return tmp;
}