Cod sursa(job #1622827)

Utilizator Stavarache.AntonioStavarache Antonio Stavarache.Antonio Data 1 martie 2016 14:47:15
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#define N 100010

using namespace std;

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

int n, m, i, j, x, y, ctc;
vector <int> g[N], gt[N], doi[N], unu;
vector <bool> uz;

void dfs (int x);
void dfst (int x);

int main()
{
    fin >> n>> m;
    for(i=1;i<=n;++i)
        uz.push_back(0);
    for(i=1;i<=m;++i)
    {
        fin >> x>> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }

    for(i=1;i<=n;++i)
    {
        if(uz[i]==0)
        {
            uz[i]=1;
            dfs(i);
        }
    }

    for(i=unu.size()-1;i>=0;--i)
    {
        if(uz[unu[i]]==1)
        {
            ctc++;
            uz[unu[i]]=0;
            dfst(unu[i]);
        }
    }

    fout<< ctc<<'\n';
    for(i=1;i<=ctc;++i)
    {
        for(j=0;j<doi[i].size();++j)
        {
            fout<< doi[i][j]<<" ";
        }
        fout<<'\n';
    }
    return 0;
}

void dfs(int x)
{
    int i;
    for(i=0;i<g[x].size();++i)
    {
        if(uz[g[x][i]]==0)
        {
            uz[g[x][i]]=1;
            dfs(g[x][i]);
        }
    }
    unu.push_back(x);
}

void dfst(int x)
{
    int i;
    for(i=0;i<gt[x].size();++i)
    {
        if(uz[gt[x][i]]==1)
        {
            uz[gt[x][i]]=0;
            dfst(gt[x][i]);
        }
    }
    doi[ctc].push_back(x);
}