Cod sursa(job #954816)

Utilizator sandruSandru Petru-Ionut sandru Data 30 mai 2013 05:57:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
using namespace std;

int n, m, nctc=-1;
vector <int> muchii1[100011];
vector <int> muchii2[100011];
vector <int> noduri;
vector <int> ctc[100011];

void citire()
{
    ifstream f("ctc.in");
    f>>n>>m;
    for(int i=0; i<m; i++)
    {   
		int a, b;
        f>>a>>b;
        muchii1[a].push_back(b);
        muchii2[b].push_back(a);
    }
    f.close ();
}

int viz[100011];

void dfs1 (int nod)
{
    viz[nod]=1;
    for(int i=0; i<muchii1[nod].size(); i++)
    {
        if (!viz[muchii1[nod][i]])
            dfs1 (muchii1[nod][i]);
    }
    noduri.push_back(nod);
}

void scriere()
{
    ofstream f("ctc.out");
    f<<nctc+1<<endl;
    for(int i=0; i<=nctc; i++)
    {
        for(int j=0; j<ctc[i].size(); j++)
            f<<ctc[i][j]<< " ";
        f<<endl;
    }
    f.close ();
}

void dfs2 (int nod)
{
    viz[nod]=1;
    ctc[nctc].push_back(nod);
    for(int i=0; i<muchii2[nod].size(); i++)
        if(!viz[muchii2[nod][i]])
			dfs2(muchii2[nod][i]);
}

int main ()
{
    citire ();
    for (int i=1; i<=n; i++)
        if (!viz[i]) 
			dfs1(i);
    memset(viz, 0, sizeof (viz));
    for(; !noduri.empty(); noduri.pop_back())
        if(!viz[noduri.back()])
        {
            ++nctc;
            dfs2(noduri.back());
        }
    scriere ();
    return 0;
}