Cod sursa(job #3375934)

Utilizator dragos_poputepopute dragos mihai dragos_popute Data 14 noiembrie 2026 13:25:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax=100000;
vector <int> g[nmax+5];
vector <int> t[nmax+4];
int n,m;
int grad[nmax+3];
int use[nmax+1],top[nmax+3],k;
int use2[nmax+3];
int nrc;
vector <int> cc[nmax+5];
void read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        g[x].push_back(y);
        t[y].push_back(x);
    }
}
void dfs(int nod)
{
    use[nod]=1;
    for(auto v:g[nod])
    {
        if(use[v]==0)
            dfs(v);
    }
    top[++k]=nod;
}
void dfs2(int nod)
{
    use2[nod]=1;
    for(auto v:t[nod])
    {
        if(use2[v]==0)
            dfs2(v);
    }
    cc[nrc].push_back(nod);
}
int main()
{   int sol;
    read();
    for(int i=1;i<=n;i++)
    {
        if(use[i]==0)
        {
            dfs(i);
        }}
    for(int i=n;i>=1;i--)
    {
        if(use2[top[i]]==0)
        {   nrc++;
            dfs2(top[i]);

        }
    }
    fout<<nrc<<endl;
    for(int i=1;i<=nrc;i++)
    {
        for(int j=0;j<cc[i].size();j++)
        {
            fout<<cc[i][j]<<" ";
        }fout<<endl;
    }
    return 0;
}