Cod sursa(job #3296227)

Utilizator radu_pipdmn bro radu_pip Data 12 mai 2025 10:24:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> vec[200005];
vector<int> vecc[200005];
vector<int> nr[200005];
queue<pair<int,int>> q;
int f[200005];
int dist[200005];
int v[200005];
int k=0;
int cnt;
void fil(int nod)
{
    if(f[nod])
        return;
    f[nod]=1;
    for(int i=0;i<vec[nod].size();i++)
    {
        fil(vec[nod][i]);
    }
    v[++k]=nod;
}
void altfil(int nod)
{
    if(f[nod]==0)
        return;
    f[nod]=0;
    nr[cnt].push_back(nod);
    for(int i=0;i<vecc[nod].size();i++)
    {
        altfil(vecc[nod][i]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        vec[a].push_back(b);
        vecc[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        fil(i);
    for(int i=n;i>=1;i--)
    {
        if(f[v[i]])
        {

        cnt++;
        altfil(v[i]);
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=0;j<nr[i].size();j++)
            cout<<nr[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}