Cod sursa(job #1936727)

Utilizator tudi98Cozma Tudor tudi98 Data 23 martie 2017 12:53:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

stack<int> S;
vector<int> G[100001];
int N,M,ID = 0;
int low[100001],id[100001];
vector< vector<int> > SCC;
bool in_stack[100001];

void tarjan(int node)
{
    low[node] = ++ID;
    id[node] = ID;
    S.push(node); in_stack[node] = 1;
    for (auto u: G[node])
    {
        if (id[u] == 0)
        {
            tarjan(u);
            low[node] = min(low[node],low[u]);
        }
        else if (in_stack[u])
            low[node] = min(low[node],low[u]);
    }

    if (low[node] == id[node])
    {
        SCC.push_back(vector<int>());
        int v;
        do {
            v = S.top(); S.pop();
            SCC.back().push_back(v);
            in_stack[v] = 0;
        } while (v != node);
    }
}

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

    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        int a,b; fin >> a >> b;
        G[a].push_back(b);
    }

    for (int i = 1; i <= N; i++)
        if (id[i] == 0)
            tarjan(i);

    fout << SCC.size() << "\n";
    for (auto v: SCC) {
        for (auto u: v)
            fout << u << " ";
        fout << "\n";
    }
}