Cod sursa(job #2423228)

Utilizator AndrulianDin Iulian Andrulian Data 20 mai 2019 22:29:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
const int nmax=100005;
vector <int> a[nmax];
vector <int> ta[nmax];
vector <int> rez[nmax];
vector <int> postordine(nmax);
vector <bool> viz(nmax);
void DFS(int x)
{
    viz[x]=1;
    for(unsigned int i=0; i<a[x].size(); i++)
        if(!viz[a[x][i]])
            DFS(a[x][i]);
    postordine.push_back(x);
}
void DFS_transpus(int x,int nrct)
{
    viz[x]=0;
    for(unsigned int i=0; i<ta[x].size(); i++)
        if(viz[ta[x][i]])
        {
            rez[nrct].push_back(ta[x][i]);
            DFS_transpus(ta[x][i],nrct);
        }

}
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x,y;
        fin>>x>>y;
        a[x].push_back(y);
        ta[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            DFS(i);

    int nrct=0;
    for(int i=postordine.size(); i>0; i--)
        if(viz[postordine[i]])
        {
            nrct++;
            rez[nrct].push_back(postordine[i]);
            DFS_transpus(postordine[i],nrct);
        }

    fout<<nrct<<"\n";
    for(int i=1; i<=nrct; i++)
        if(rez[i].size()>0)
        {
            for(unsigned int j=0; j<rez[i].size(); j++)
                fout<<rez[i][j]<<" ";
            fout<<"\n";
        }
}