Cod sursa(job #2523910)

Utilizator RedXtreme45Catalin RedXtreme45 Data 14 ianuarie 2020 21:02:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <vector>
#include <cstring>
#define Nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,ap[Nmax],u,fina[Nmax],nr;
vector <int> G[Nmax],Gt[Nmax],Sol[Nmax];
void DFS(int start){
    ap[start]=1;
    for (auto i:G[start]){
        if (ap[i]==0)
        {
            DFS(i);
        }
    }
    u++;
    fina[u]=start;
}
void DFSt(int start){
    ap[start]=1;
    for (auto i:Gt[start]){
        if (ap[i]==0)
        {
            DFSt(i);
        }
    }
    Sol[nr].push_back(start);
}
int main()
{
    int i,a,b,j;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>a>>b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
    for (i=1;i<=n;i++)
    {
        if (ap[i]==0)
            DFS(i);
    }
    memset(ap,0,sizeof ap);
    for (i=n;i>=1;i--){
        if (ap[fina[i]]==0){
            nr++;
            DFSt(fina[i]);
        }
    }
    fout<<nr<<"\n";
    for (i=1;i<=nr;i++)
    {
        for (auto j:Sol[i])
            fout<<j<<" ";
        fout<<"\n";
    }
    return 0;
}