Cod sursa(job #3003423)

Utilizator FilippclaudiuFilip CLaudiu Filippclaudiu Data 15 martie 2023 18:44:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int nmax=1e5+5;
int n,m,viz[nmax],nr;
vector<int> g[nmax],gr[nmax],rez[nmax];
stack<int> parc;
void dfs(int x)
{
    viz[x]=1;
    for(auto i:g[x])
    {
        if(viz[i]==0)
        {
            dfs(i);
        }
    }
    parc.push(x);
}
void dfs2(int x)
{
    viz[x]=2;
    rez[nr].push_back(x);
    for(auto i:gr[x])
    {
        if(viz[i]==1)
            dfs2(i);
    }
}
void afis()
{
    cout<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
        for(auto j:rez[i])
            cout<<j<<" ";
        cout<<"\n";
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        gr[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            dfs(i);
    while(!parc.empty())
    {
        int x=parc.top();
        if(viz[x]==1)
        {
            nr++;
            dfs2(x);
        }
        parc.pop();
    }
    afis();
}