Cod sursa(job #1919671)

Utilizator razvanlgu31Razvan Lungu razvanlgu31 Data 9 martie 2017 20:30:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,i,j,x,y,viz[100010],viz1[100010],s[100010],k=0,nr=0;
vector <int> g[100010],gt[100010];
vector <int> a[100010];
void dfs(int x)
{

//    fout<<x<<" ";
    viz[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        if(viz[g[x][i]]==0)
            dfs(g[x][i]);
    }
    s[++k]=x;
}
void dfs1(int x)
{
    viz1[x]=1;
    a[nr].push_back(x);
    for(int i=0;i<gt[x].size();i++)
    {
        if(viz1[gt[x][i]]==0)
            dfs1(gt[x][i]);
    }

}
int main()
{
    fin>>n>>m;
    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(viz[i]==0)
        {
            dfs(i);
        }
    }
    for(i=n;i>=1;i--)
    {
        if(viz1[s[i]]==0)
        {
            nr++;
            dfs1(s[i]);
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(j=0;j<a[i].size();j++)
            fout<<a[i][j]<<" ";
        fout<<'\n';
    }
//    for(i=1;i<=n;i++)
//    {
//        fout<<i<<" ";
//        for(j=0;j<g[i].size();j++)
//            fout<<g[i][j]<<" ";
//        fout<<s[i]<<'\n';
//    }
    return 0;
}