Cod sursa(job #1385692)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 12 martie 2015 11:29:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100000
using namespace std;

typedef vector <int> graf;
typedef stack <int> stiva;
typedef vector <int> ctc;

graf G[MAXN + 1];
int index[MAXN + 1], lowlink[MAXN + 1];
bool in_Stack[MAXN + 1];
stiva S;
vector <ctc> sol;
int ind = 1;

void dfs(int node) {
    index[node] = lowlink[node] = ind;
    ++ind;
    in_Stack[node] = true;
    S.push(node);
    for (graf :: iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
        if (!index[*it]) {
            dfs(*it);
            if (lowlink[*it] < lowlink[node])
                lowlink[node] = lowlink[*it];
        }
        else if (in_Stack[*it])
            if (lowlink[*it] < lowlink[node])
                lowlink[node] = lowlink[*it];
    }

    if (index[node] == lowlink[node]) {
        ctc comp;
        int nd;
        do {
            nd = S.top();
            S.pop();
            in_Stack[nd] = false;
            comp.push_back(nd);
        }
        while (nd != node);
        sol.push_back(comp);
    }
}

int main () {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int n, m;
    fin >> n >> m;
    for (int i = 0 ; i < m ; ++i) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
    }

    for (int i = 1 ; i <= n ; ++i)
        if (index[i] == 0)
            dfs(i);

    fout << sol.size() << "\n";
    for (int i = 0 ; i < sol.size() ; ++i, fout << "\n")
        for (int j = 0 ; j < sol[i].size() ; ++j)
            fout << sol[i][j] << " ";

    return 0;
}