Cod sursa(job #1681024)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 9 aprilie 2016 11:10:54
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstdlib>
#include <vector>
#define NM 100005

using namespace std;


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

vector <int> N[NM];

int n, m,i,viz[201],post[201],nrc,nr;

vector <int> a[NM], at[NM];


void citire()
{
    int i, x, y;
    fin>>n>>m;;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;

        a[x].push_back(y);
        at[y].push_back(x);

    }
}
void dfs(int i)
{
    int j;
    viz[i]=1;
    for(j=0; j<a[i].size(); j++)
        if(!viz[a[i][j]])
            dfs(a[i][j]);
    post[++nr]=i;
}
void dfst(int i)
{
    int j;
    viz[i]=0;
    for(j=0; j<at[i].size();j++)
        if(viz[at[i][j]])
            dfst(at[i][j]);
    N[nrc].push_back(i);
}
int main()
{
    int j;
    citire();

    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);

    for(i=n;i>=1;i--)
        if(viz[post[i]])
        {
            nrc++;
            dfst(post[i]);
        }
    fout<<nrc<<'\n';
    for (i=1; i<=nrc; i++)
    {
        for (j=N[i].size()-1; j>=0; j--)
            fout<<N[i][j]<<" ";
        fout<<'\n';
    }
    fout.close();
    return 0;
}