Cod sursa(job #1323597)

Utilizator western100Sutu Eusebiu western100 Data 21 ianuarie 2015 12:02:36
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <stack>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,index,k;
vector < list < int > > a,b;
stack < int > s;

struct tip
{
    int index,lowlink;
    bool st;
};

vector < tip > viz;

void citire()
{
    int x,y;
    f>>n>>m;
    a.resize(n+1);
    viz.resize(n+1);
    b.resize(n+1);
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
    }
}

void dfsctc(int v)
{
    viz[v].index=index;
    viz[v].lowlink=index;
    index++;
    s.push(v);
    viz[v].st=true;
    list< int > :: iterator it;
    for(it=a[v].begin();it!=a[v].end();it++)
    {
        if(!viz[*it].index)
        {
            dfsctc(*it);
            viz[v].lowlink=min(viz[v].lowlink,viz[*it].lowlink);
        }
        else if(viz[*it].st)
        {
            viz[v].lowlink=min(viz[v].lowlink,viz[*it].index);
        }
    }
    if(viz[v].lowlink==viz[v].index)
    {
        k++;
        while(s.top()!=v)
        {
            b[k].push_back(s.top());
            s.pop();
        }
        s.pop();
        b[k].push_back(v);
    }
}

void afis()
{
    int i;
    list<int>::iterator it;
    g<<k<<'\n';
    for(i=1;i<=k;i++)
    {
        for(it=b[i].begin();it!=b[i].end();it++)
            g<<*it<<' ';
        g<<'\n';
    }
}
int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(!viz[i].index)
            dfsctc(i);
    afis();
    return 0;
}