Cod sursa(job #1119702)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 24 februarie 2014 19:36:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <stack>
#include <vector>

using namespace std;


const int N = 100005;
const int M = 200005;


int n, m;
int id;
int ord[N], low[N];
bool inStack[N];
stack <int> s;
vector <int> graph[N];
vector <vector <int> > ans;


void read() {
    freopen("ctc.in", "r", stdin);

    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);
    }
}

vector <int> build_comp(int start) {
    vector <int> comp;

    int node;

    do {
        node = s.top();
        s.pop();
        inStack[node] = false;

        comp.push_back(node);
    } while (node != start);

    return comp;
}

void tarjan(int node) {
    ord[node] = low[node] = id;
    ++id;

    s.push(node);
    inStack[node] = true;

    for (vector <int>::iterator it = graph[node].begin(); it != graph[node].end(); ++it) {
        if (ord[*it] == -1) {
            tarjan(*it);
            low[node] = min(low[node], low[*it]);
        } else if (inStack[*it])
            low[node] = min(low[node], low[*it]);
    }

    if (ord[node] == low[node])
        ans.push_back(build_comp(node));
}

void print() {
    freopen ("ctc.out", "w", stdout);
    
    int nrComp = ans.size();
    printf("%d\n", nrComp);

    for (int i = 0; i < nrComp; ++i) {
        for (int j = 0; j < ans[i].size(); ++j)
            printf("%d ", ans[i][j]);
        
        printf("\n");
    }
}

int main() {
    read();
 
    memset(ord, -1, sizeof(ord));
    for (int i = 1; i <= n; ++i)
        if (ord[i] == -1)
            tarjan(i);
    
    print();
}