Cod sursa(job #3041825)

Utilizator stefantagaTaga Stefan stefantaga Data 1 aprilie 2023 21:28:25
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;
int n,m,i,x,y,nr[100005];
vector <int> v[100005],inv[100005];
int viz[100005],q,nrcomp;
vector <int> sal[100005];
void dfs(int x)
{
    int i;
    viz[x]=1;
    for (int i=0;i<v[x].size();i++)
    {
        int nod = v[x][i];
        if (viz[nod]==0)
        {
            dfs(nod);
        }
    }
    nr[++q]=x;
}
void dfs2(int x)
{
    viz[x]=1;
    sal[nrcomp].push_back(x);
    for (int i=0;i<inv[x].size();i++)
    {
        int nod = inv[x][i];
        if (viz[nod]==0)
        {
            dfs2(nod);
        }
    }
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
        inv[y].push_back(x);
    }
    q=0;
    for (i=1;i<=n;i++)
    {
        if (viz[i]==0)
        {
            dfs(i);
        }
    }
    for (i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    for (i=q;i>=1;i--)
    {
        int nod = nr[i];
        if (viz[nr[i]]==0)
        {
            nrcomp++;
            dfs2(nr[i]);
        }
    }
    cout<<nrcomp<<'\n';
    for (i=1;i<=nrcomp;i++)
    {
        sort(sal[i].begin(),sal[i].end());
        for (int j=0;j<sal[i].size();j++)
        {
            cout<<sal[i][j]<<" ";
        }
        cout<<'\n';
    }
    return 0;
}