Cod sursa(job #3296213)

Utilizator FlaviuuuFlaviu Flaviuuu Data 12 mai 2025 10:13:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream cin("bfs.in");
ofstream cout("bfs.out");
#define ll int
vector<vector<ll>> t(100005), a(100005);
ll nr = 0;
const int siz = 100005;
bitset<siz> vis;
vector<vector<ll>> cn(100005);
vector<ll> ord;
void dfs(ll x)
{
    vis[x] = 1;
    for(int i = 0; i < a[x].size(); i++)
        if(vis[a[x][i]] == 0)
            dfs(a[x][i]);
    ord.push_back(x);
}
void dfst(ll x)
{
    vis[x] = 1;
    cn[nr].push_back(x);
    for(int i = 0; i < t[x].size(); i++)
        if(vis[t[x][i]] == 0)
            dfst(t[x][i]);
}
int main()
{
    ll n, m, x, y, s;
    cin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        cin>>x>>y;
        a[x].push_back(y);
        t[y].push_back(x);
    }
    for(int i = 1; i <= n; i++)
        if(vis[i] == 0)
            dfs(i);
        vis.reset();
    for(int i = ord.size() - 1; i >= 0; i--)
        if(vis[ord[i]] == 0)
            nr++, dfst(ord[i]);
    cout<<nr<<'\n';
    for(int i = 1; i <= nr; i++)
    {
        for(int j = 0; j < cn[i].size(); j++)
            cout<<cn[i][j]<<" ";
        cout<<'\n';
    }
    return 0;
}