Cod sursa(job #1922930)

Utilizator roxi22Roxi C. roxi22 Data 10 martie 2017 19:39:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

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

#define nmax 100005

int n,m,nrc,x,y,viz[nmax],vizt[nmax],stiva[nmax],vf;
vector<int> g[nmax],gt[nmax],c[nmax];

void dfs(int nod)
{
    viz[nod]=1;
    int l=g[nod].size();
    for(int i=0;i<l;i++)
        {int nodC=g[nod][i];
        if(!viz[nodC])
            dfs(nodC);}
    stiva[++vf]=nod;
}

void dfst(int nod)
{
    c[nrc].push_back(nod);
    vizt[nod]=1;
    int l=gt[nod].size();
    for(int i=0;i<l;i++){
        int nodc=gt[nod][i];
        if(!vizt[nodc])
            dfst(nodc);}

}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        {fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);}
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    for(int i=n;i>=1;i--)
        if(!vizt[stiva[i]])
            {nrc++;
            dfst(stiva[i]);}
    fout<<nrc<<"\n";
    for(int i=1;i<=nrc;i++)
        {   int l=c[i].size();
            for(int j=0;j<l;j++)
                fout<<c[i][j]<<" ";
            fout<<"\n";
        }


    return 0;
}