Cod sursa(job #2789215)

Utilizator francescom_481francesco martinut francescom_481 Data 27 octombrie 2021 09:36:45
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include<bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cin fin
#define cout fout

#define N 100005
vector < vector < int > > g, gt, ans;
stack < int > s;
int n, m, x, y, f[N], vis[N], sol;

void df1(int x)
{
    vis[x] = 1;
    for(auto t : g[x])
    {
        int T = t;
        if(vis[T] == 0)
        {
            df1(T);
        }
    }
    s.push(x);
}
void df2(int x)
{
    vis[x] = 0;
    for(auto t : gt[x])
    {
        int T = t;
        if(vis[T] == 1)
        {
            df2(T);
        }
    }
    ans[sol].push_back(x);
    f[x] = sol;
}

int main()
{
    cin >> n >> m;
    g.resize(n+5);
    gt.resize(n+5);
    ans.resize(n+5);
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(vis[i] == 0)
        {
            df1(i);
        }
    }
    while(!s.empty())
    {
        while(!s.empty()  &&  vis[s.top()] == 0)
        {
            s.pop();
        }
        if(!s.empty())
        {
            sol++;
            df2(s.top());
            s.pop();
        }
    }
    cout << sol << '\n';
    for(int i = 1 ; i <= n ; i++)
    {
        if(f[i])
        {
            int nr = f[i];
            sort(ans[nr].begin(),ans[nr].end());
            cout << ans[nr].size() << " ";
            for(auto t : ans[nr])
            {
                int T = t;
                cout << T << " ";
                f[T] = 0;
            }
            cout << '\n';
        }
    }
    return 0;
}