Cod sursa(job #1464877)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 25 iulie 2015 22:06:52
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
 
int n,m,x,y,viz[NMAX],postordine[NMAX],nr,nrc;
vector<int> a[NMAX],ta[NMAX];
vector<int> solutii[NMAX];
 
void DFS(int nod)
{
    viz[nod]=1;
    for(int i=0;i<a[nod].size();i++)
    {
        if(!viz[a[nod][i]])
            DFS(a[nod][i]);
    }
    postordine[++nr]=nod;
    //cout << nr << " " << postordine[nr] << endl;
}
 
void DFST(int nod)
{
    viz[nod]=0;
    solutii[nrc].push_back(nod);
    for(int i=0;i<ta[nod].size();i++)
        if(viz[ta[nod][i]])
            DFST(ta[nod][i]);
}
 
int main()
{
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    in >> n >> m;
    for(int i=0;i<m;i++)
    {
        in >> x >> y;
        a[x].push_back(y);
        ta[y].push_back(x);
    }
 
    for(int i=1;i<=n;i++)
        if(!viz[i]){
            DFS(i);
        }
 
    for(int i=n;i>0;i--)
        if(viz[postordine[i]])
    {
        //cout << i << " ";
        nrc++;
        DFST(postordine[i]);
    }
    out << nrc << "\n";
    for(int i=1;i<=nrc;i++)
    {
        for(int j=0;j<solutii[i].size();j++)
            out << solutii[i][j] << " ";
        out << "\n";
    }
    return 0;
}