Cod sursa(job #3319781)

Utilizator alexdraguAlexandru Dragu alexdragu Data 3 noiembrie 2025 11:27:12
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> v[100005],g[100005],sol[100005];
int n,m,i,x,y,j,nr,ctc[100005];
bool viz1[100005],viz2[100005];
void dfs(int nod)
{
    viz1[nod]=1;
    for(auto x:v[nod])
    {
        if(viz1[x]==0) dfs(x);
    }
}
void dfs2(int nod)
{
    viz2[nod]=1;
    for(auto x:g[nod])
    {
        if(viz2[x]==0) dfs2(x);
    }
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(ctc[i]==0)
        {
            for(j=1;j<=n;j++) {viz1[j]=viz2[j]=0;}
            nr++;
            dfs(i);dfs2(i);
            for(j=1;j<=n;j++)
            {
                if(viz1[j]==1&&viz2[j]==1) {ctc[j]=nr;sol[nr].push_back(j);}
            }
        }
    }
    cout<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(auto x:sol[i]) cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}