Cod sursa(job #857507)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 17 ianuarie 2013 21:28:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define DN 100005
#define pb push_back
#define un unsigned
using namespace std;

vector<int> list[DN],v,liste[DN];
stack<int> s;
bool viz[DN];
int index[DN],min_index[DN],sz=0;

void dfs(int nod)
{
    s.push(nod);
    viz[nod]=true;
    index[nod]=++index[0];
    min_index[nod]=index[nod];

    for(un int i=0;i<list[nod].size();++i)
    {
        int next_nod=list[nod][i];
        if(!index[next_nod])
            {
                dfs(next_nod);
                min_index[nod]=min(min_index[nod],min_index[next_nod]);
            }
            else if(viz[next_nod])
                min_index[nod]=min(min_index[nod],index[next_nod]);
    }
    if(min_index[nod]==index[nod])
    {
        ++sz;
        int a;
        while(a!=nod)
        {
            a=s.top();
            liste[sz].pb(a);
            viz[a]=false;
            s.pop();
        }
    }
}

int main()
{
    int n,m;
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(;m;--m)
    {
        int x,y;
        f>>x>>y;
        list[x].pb(y);
    }
    for(int i=1;i<=n;++i)
        if(!index[i])
            dfs(i);
    if(s.size())
    {
        ++sz;
        while(s.size())
        {
            liste[sz].pb(s.top());
            s.pop();
        }
    }
    g<<sz<<"\n";
    for(int i=1;i<=sz;++i)
    {
        for(un int j=0;j<liste[i].size();++j)
            g<<liste[i][j]<<" ";
        g<<"\n";
    }

    return 0;
}