Cod sursa(job #1947804)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 31 martie 2017 13:16:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
/**
  *  Worg
  */
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>

using std::stack;
using std::vector;
FILE *fin = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

const int kMaxN = 1 + 100000;

/*-------- Input data --------*/
int N, M;
vector<int > graph[kMaxN];
/*-------- SCC data --------*/
stack<int > my_stack;
bool in_stack[kMaxN];

int index[kMaxN], lowlink[kMaxN];
int crt_index;

vector<int > scc;
vector<vector<int > > scc_list;
/*-------- --------*/

void ReadInput() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int x, y; scanf("%d%d", &x, &y);
        graph[x].push_back(y);
    }
}

void DFS(int node) {
    crt_index ++;
    index[node] = lowlink[node] = crt_index;

    my_stack.push(node); in_stack[node] = true;
    for(int nxt : graph[node]) {
        if(!index[nxt]) {
            DFS(nxt);
            lowlink[node] = std::min(lowlink[node], lowlink[nxt]);
        } else if(in_stack[nxt]) {
            lowlink[node] = std::min(lowlink[node], index[nxt]);
        }
    }

    if(lowlink[node] == index[node]) {
        scc.clear();
        int now;
        do {
            now = my_stack.top(); my_stack.pop();
            scc.push_back(now); in_stack[now] = false;
        }while(now != node);
        scc_list.push_back(scc);
    }
}

void TarjanAlgo() {
    crt_index = 0;
    for(int i = 1; i <= N; i++) {
        if(!index[i]) {
            DFS(i);
        }
    }
}

void WriteOutput() {
    printf("%d\n", (int)scc_list.size());
    for(auto comp : scc_list) {
        for(auto node : comp) {
            printf("%d ", node);
        }
        printf("\n");
    }
}

int main() {
    ReadInput();
    TarjanAlgo();
    WriteOutput();
    return 0;
}