Cod sursa(job #1408561)

Utilizator T.C.11Tolan Cristian T.C.11 Data 30 martie 2015 09:09:20
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda sim_oni_2010_ziua1 Marime 1.54 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

int n,m,i,j,s[100001],x,y,nr,k,f[100001];

vector<int> v[100001],vv[100001];
stack<int> q;

void dfs(int nod, bool afisare)
{
    for (vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); it ++)
    {
        if (s[*it]==0)
        {
            q.push(*it);
            s[*it]=1;
            if (afisare == true)
                fout<<*it<<" ";
            dfs(*it,afisare);
        }
    }
    k++;
    f[k]=nod;
    q.pop();
}

void dfsvv(int nod, bool afisare)
{
    for (vector<int>::iterator it = vv[nod].begin(); it != vv[nod].end(); it ++)
    {
        if (s[*it]==0)
        {
            s[*it]=1;
            if (afisare == true)
                fout<<*it<<" ";
            dfsvv(*it,afisare);
        }
    }
}

int main()
{
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        vv[y].push_back(x);
    }
    q.push(1);
    s[1]=1;
    dfs(1,false);
    for (i=1;i<=n;i++)
        s[i]=0;
    for (i=k;i>=1;i--)
    {
        if (s[f[i]]==0)
        {
            s[f[i]]=1;
            dfsvv(f[i],false);
            nr++;
        }
    }
    fout<<nr<<"\n";
    for (i=1;i<=n;i++)
        s[i]=0;
    for (i=k;i>=1;i--)
    {
        if (s[f[i]]==0)
        {
            s[f[i]]=1;
            fout<<f[i]<<" ";
            dfsvv(f[i],true);
            fout<<"\n";
        }
    }
    return 0;
}