Cod sursa(job #2195496)

Utilizator stefantagaTaga Stefan stefantaga Data 16 aprilie 2018 15:49:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[100002];
int viz[100002],viz2[100002],n;
int x[100002];
vector <int> v2[100002];
vector <int> v3[100002];
int timp,ntc;
void df(int vf)
{
    vector <int> :: iterator it;
    viz[vf]=1;
    for (it=v[vf].begin();it!=v[vf].end();it++)
    {
        if (!viz[*it])
        {
            df(*it);
        }
    }
    timp++;
    x[n+1-timp]=vf;
}
void df2(int vf)
{
    vector <int> :: iterator it;
    viz2[vf]=1;
    for (it=v2[vf].begin();it!=v2[vf].end();it++)
    {
        if (!viz2[*it])
        {
            df2(*it);
        }
    }
    v3[ntc].push_back(vf);
}
int m,i,x1,y;
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x1>>y;
        if (x1!=y)
        {
            v2[y].push_back(x1);
            v[x1].push_back(y);
        }
    }
    for (i=1;i<=n;i++)
    {
        if (viz[i]==0)
        {
            df(i);
        }
    }
    ntc=0;
    for (i=1;i<=n;i++)
    {
        if (viz2[x[i]]==0)
        {
            ntc++;
            df2(x[i]);
        }
    }
    g<<ntc<<'\n';
    for (i=1;i<=ntc;i++)
    {
        vector <int> :: iterator it;
        for (it=v3[i].begin();it!=v3[i].end();it++)
        {
            g<<*it<<" ";
        }
        g<<'\n';
    }
    return 0;
}