Cod sursa(job #1291073)

Utilizator marian98Horodnic Gheorghe Marian marian98 Data 12 decembrie 2014 10:32:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
unsigned long n,m,nr,nrc;
vector<unsigned>A[100001],AT[100001],Solutii[100001];
vector<bool>viz(100001,0);
unsigned long postordine[100001],indice=0;
ofstream f1("ctc.out");
void DFS(unsigned long x)
{
    viz[x]=1;
    for (unsigned long i=1;i<=A[x].size()-1;i++)
        if (!viz[A[x][i]])  DFS(A[x][i]);
    postordine[++nr]=x;
}
void DFST(unsigned long x)
{
    viz[x]=0;
    Solutii[indice].push_back(x);
    for (unsigned long i=1;i<=AT[x].size()-1;i++)
        if (viz[AT[x][i]])  DFST(AT[x][i]);
}
void citire()
{
    ifstream f("ctc.in");
    f>>n>>m;
    for (unsigned long i=1;i<=n;i++)
    {
        A[i].push_back(0);
        AT[i].push_back(0);
    }
    for (unsigned long i=1;i<=m;i++)
    {
        unsigned long a,b;
        f>>a>>b;
        A[a].push_back(b);
        AT[b].push_back(a);
    }
}
int main()
{
    citire();
    for (unsigned long i=1;i<=n;i++)
        if (!viz[i]) DFS(i);
    for (unsigned long i=n;i>0;i--)
        if (viz[postordine[i]])
        {
            indice++;
            DFST(postordine[i]);
            nrc++;
        }
    f1<<nrc<<"\n";
    for (unsigned long i=1;i<=indice;i++)
        {
            for (unsigned long j=0;j<=Solutii[i].size()-1;j++)
                f1<<Solutii[i][j]<<" ";
            f1<<"\n";
        }
    return 0;
}