Cod sursa(job #973819)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 15 iulie 2013 17:33:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#define maxn 100001

using namespace std;

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

vector <int> G[maxn],CC[maxn];
int stack[maxn],order[maxn],lowest_in[maxn],visited[maxn],is_in_stack[maxn];
int n,m,lvl,current,nr,a,b;

void Tarjan (int x)
{
    visited[x]=1;
    order[x]=++current;
    lowest_in[x]=order[x];
    is_in_stack[x]=1;

    stack[++lvl]=x;

    for (vector<int>::iterator it=G[x].begin(); it!=G[x].end(); ++it)
    {
        if (!visited[*it])
        {
            Tarjan (*it);
            lowest_in[x] = min (lowest_in[x],lowest_in[*it]);
        }
        else if (is_in_stack[*it])
            lowest_in[x] = min (lowest_in[x],order[*it]);
    }

    if (order[x]==lowest_in[x])
    {
        ++nr;
        while (stack[lvl]!=x)
        {
            CC[nr].push_back(stack[lvl]);
            is_in_stack[stack[lvl]]=0;
            lvl--;
        }
        CC[nr].push_back (x);
        is_in_stack[x]=0;
        lvl--;
    }
}

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 (!visited[i]) Tarjan (i);
    }

    fout<<nr<<"\n";
    for (int i=1; i<=nr; i++)
    {
        for (vector<int>::iterator it=CC[i].begin(); it!=CC[i].end(); ++it)
            fout<<*it<<" ";
        fout<<"\n";
    }
}