Cod sursa(job #1468673)

Utilizator tudi98Cozma Tudor tudi98 Data 6 august 2015 17:48:57
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int Nmax = 100001;

int N,M;
vector<int> Adj[Nmax];
int lowlink[Nmax];
int link[Nmax];
bool seen[Nmax];
int idx = 0;
stack<int> S;
vector< vector<int> > Comp;

void Tarjan(int node)
{
    lowlink[node] = ++idx;
    link[node] = idx;
    seen[node] = 1;
    S.push(node);

    for(vector<int>::iterator it = Adj[node].begin(); it != Adj[node].end(); ++it)
    {
        if(seen[*it])
            lowlink[node] = min(lowlink[node],lowlink[*it]);
        else
        {
            Tarjan(*it);
            lowlink[node] = min(lowlink[node],lowlink[*it]);
        }
    }

    if(link[node] == lowlink[node])
    {
        Comp.push_back(vector<int>());
        while(S.top() != node)
        {
            Comp.back().push_back(S.top());
            S.pop();
        }

        Comp.back().push_back(S.top());
        S.pop();
    }
}

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;
        Adj[a].push_back(b);
    }

    for(int i = 1; i <= N; i++)
        if(!seen[i])
            Tarjan(i);

    fout << Comp.size() << "\n";
    for(int i = 0; i < Comp.size(); i++)
    {
        for(int j = 0; j < Comp[i].size(); j++)
            fout << Comp[i][j] << " ";
        fout << "\n";
    }
}