Cod sursa(job #3204785)

Utilizator Raul_AArdelean Raul Raul_A Data 17 februarie 2024 14:19:20
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define pii pair<int, int>
#define tpl tuple<int, int, int>
#define oo 0x3f3f3f3f
using namespace std;

const string fn("ctc");

ifstream in(fn + ".in");
ofstream out(fn + ".out");

#define cin in
#define cout out

const int MAX=1e5;

int n,m;
vector<int> g[MAX+5],gt[MAX+5],s,ans;
vector<vector<int>> ctc;
bitset<MAX+5> viz;

void read()
{
    cin>>n>>m;

    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        g[x].eb(y);
        gt[y].eb(x);
    }
}

void dfs(int node)
{
    viz[node]=1;
    for(auto x: g[node])
        if(!viz[x])
            dfs(x);
    
    s.eb(node);
}

void dfst(int node)
{
    viz[node]=0;
    ans.eb(node);
    for(auto x: gt[node])
        if(viz[x])
            dfst(x);
}

int main()
{
    read();
    for(int i=1;i<=n;i++)
        if(!viz[i]) 
            dfs(i);
    
    while(!s.empty())
    {
        int node=s.back();
        s.pop_back();

        if(viz[node])
        {
            dfst(node);
            if(ans.size()>1)
            {
                sort(ans.begin(),ans.end());
                ctc.eb(ans);
            }
            ans.clear();
        }
    }

    cout<<ctc.size()<<'\n';
    for(auto it: ctc)
    {
        for(auto x: it)
            cout<<x<<' ';
        cout<<'\n';
    }
    return 0;
}