Cod sursa(job #2972838)

Utilizator GILIEDAVIDGilie David Florin GILIEDAVID Data 30 ianuarie 2023 15:11:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,nr,viz[100001];
vector<int> v1[100001],v2[100001],sol[100001];
stack<int> s;

void dfs1(int nod)
{
    viz[nod]=1;
    for(int i=0;i<v1[nod].size();i++)
        if(!viz[v1[nod][i]])
            dfs1(v1[nod][i]);
    s.push(nod);
}

void dfs2(int nod)
{
    sol[nr].push_back(nod);
    viz[nod]=1;
    for(int i=0;i<v2[nod].size();i++)
        if(!viz[v2[nod][i]])
            dfs2(v2[nod][i]);
}

void solve()
{
     for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs1(i);
     memset(viz,0,sizeof(viz));
     for(int i=1;i<=n;i++)
     {
         int x=s.top();
         if(!viz[x])
         {
             nr++;
             dfs2(x);
         }
         s.pop();
     }
     g<<nr<<'\n';
     for(int i=1;i<=nr;i++)
     {
         for(int j=0; j<sol[i].size();j++)
            g<<sol[i][j]<<" ";
         g<<'\n';
     }
}
int main()
{
    int x,y;
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    solve();
    return 0;
}