Cod sursa(job #2971892)

Utilizator BalanelBalan Stefan Balanel Data 28 ianuarie 2023 11:53:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,x,y,f[100001],nr;
vector<int> v1[100001],v2[100001],sol[100001];
stack<int> s;
void dfs1(int k)
{f[k]=1;
for(int i=0;i<v1[k].size();i++)
    if(!f[v1[k][i]]) dfs1(v1[k][i]);
s.push(k);
}
void dfs2(int k)
{sol[nr].push_back(k);
f[k]=1;
for(int i=0;i<v2[k].size();i++)
    if(!f[v2[k][i]]) dfs2(v2[k][i]);
}
void solve()
{
for(int i=1;i<=n;i++)
    if(!f[i]) dfs1(i);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
    {if(!f[s.top()]) nr++,dfs2(s.top());
    s.pop();}
out<<nr<<'\n';
for(int i=1;i<=nr;i++)
    {for(int j=0;j<sol[i].size();j++)
         out<<sol[i][j]<<' ';
    out<<'\n';
    }
}
int main()
{in>>n>>m;
for(int i=1;i<=m;i++)
    {in>>x>>y;
    v1[x].push_back(y);
    v2[y].push_back(x);}
solve();
return 0;
}