Cod sursa(job #2767812)

Utilizator CelestinNegraru Celestin Celestin Data 7 august 2021 21:34:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define maxi 100000
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,cnt;
vector<int> G[1+maxi],GT[1+maxi],SOL[1+maxi],F;
vector<int>::iterator I;
bool viz1[1+maxi],viz2[1+maxi];
void READ()
{
    int a,b;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    f.close();
    return;
}
void DFS(int x)
{
    viz1[x]=true;
    for(auto a:G[x])
        if(!viz1[a])
         DFS(a);
    F.push_back(x);
}
void DFSGT(int x,int cnt)
{
    viz2[x]=true;
    SOL[cnt].push_back(x);
    for(auto a:GT[x])
        if(!viz2[a])
         DFSGT(a,cnt);
}
void KOSARAJU()
{
    for(int i=1;i<=n;i++)
        if(!viz1[i])
         DFS(i);
    for(I=F.end()-1;I>=F.begin();I--)
    {
        if(!viz2[*I])
            cnt++,DFSGT(*I,cnt);
    }
    g<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
        sort(SOL[i].begin(),SOL[i].end());
    for(int i=1;i<=cnt;i++)
    {
        for(auto a:SOL[i])
            g<<a<<" ";
        g<<'\n';
    }
    g.close();
    return;

}
int main()
{
    READ();
    KOSARAJU();
    return 0;
}