Cod sursa(job #2944952)

Utilizator szaszdavidSzasz David szaszdavid Data 23 noiembrie 2022 10:16:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <vector>
#define NMax 200005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> g[NMax],gt[NMax],ctc[NMax];
int use[100005]={0};
int order[100005],k,nrc,n,m;
void read()
{
    int i,x,y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
void dfs(int v)
{
    int i;
    use[v]=1;
    for(i=0;i<g[v].size();i++)
    {
        if(use[g[v][i]] == 0)
            dfs(g[v][i]);
    }
    order[++k]=v;
}
void dfs2(int v)
{
    int i;
    use[v]=0;
    ctc[nrc].push_back(v);
    for(i=0;i<gt[v].size();i++)
    {
        if(use[gt[v][i]] == 1)
            dfs2(gt[v][i]);
    }

}
void kosaraju()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        if(use[i]==0) dfs(i);
    }
    for(i=n;i>=1;i--)
    {
        if(use[order[i]]==1)
        {
            nrc++;
            dfs2(order[i]);
        }
    }
    fout<<nrc<<"\n";
    for(i=1;i<=nrc;i++)
    {
        for(j=0;j<ctc[i].size();j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
    }
}
int main()
{
    read();
    kosaraju();
    return 0;
}