Cod sursa(job #1967605)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 16 aprilie 2017 20:55:43
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
 
 
using namespace std;
const int kMaxN = 1e5+10; 

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
 
vector<int> G[kMaxN], CC[kMaxN];
int lowlink[kMaxN], depth[kMaxN], current, stack[kMaxN], n, m, a, b, t, nr;
bool is_in_stack[kMaxN];
 
void tarjan(int x) {
    lowlink[x] = depth[x];
    is_in_stack[x] = 1;
    stack[++t] = x;

    for (auto y : G[x]) {
        if (is_in_stack[y]) {
            lowlink[x] = min(lowlink[x], lowlink[y]);
        }
    }
 
    for (auto y : G[x]) {
        if (!depth[y]) {
            depth[y] = depth[x] + 1;
            tarjan(y);
            lowlink[x] = min(lowlink[x], lowlink[y]);
        }
    }
 
    if (lowlink[x] == depth[x]) {
        ++nr;
        while (stack[t] != x) {
            CC[nr].push_back(stack[t]);
            is_in_stack[stack[t]] = 0;
            --t;
        }
        CC[nr].push_back(x);
        is_in_stack[x] = 0;
        --t;
    }
}
 
int main()
{
    fin >> n >> m;
 
    for (int i = 1; i <= m; ++i) {
        fin >> a >> b;
        G[a].push_back (b);
    }
 
    for (int i = 1; i <= n; ++i) {
        if (!depth[i]) {
            depth[i] = 1;
            tarjan(i);
        }
    }
 
    fout << nr << "\n";
 
    for (int i = 1; i <= nr; ++i) {
        for (auto el : CC[i]) {
            fout << el << " ";
        }
        fout << "\n";
    }
}