Cod sursa(job #2180066)

Utilizator nick12nicolae mihalache nick12 Data 20 martie 2018 16:54:17
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;



#define pp pair<int,int>
#define oo 100000000
#define RRR ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define int ll
vector <int> ar[100001];
vector <int> ar2[100001];
int viz[100001];

vector <int> L;
void vis(int i)
{
    viz[i] = 1;
    for (int j=0;j<ar[i].size();j++)
    {
        if (viz[ar[i][j]] == 0)
            vis(ar[i][j]);
    }
    L.push_back(i);
}
int u;
vector <int> rs[100001];
void dfs(int i)
{
    viz[i] = 1;
  //  cout << i << " ";
    rs[u].push_back(i);
    for (int j=0;j<ar2[i].size();j++)
    {
        if (viz[ar2[i][j]] == 0) 
        {
            dfs(ar2[i][j]);
        }
    }
}
int n,m;
int32_t main()
{RRR
    cin >> n >> m;
    int a,b;
    for (int i=0;i<m;i++)
    {
        cin >> a >> b;
        ar[a].push_back(b);
        ar2[b].push_back(a);
    }
    for (int i=1;i<=n;i++)
    {
        if (viz[i] == 0)
         vis(i);
    }
    for (int i=0;i<=n;i++)viz[i] = 0;
    while (L.size())
    {
        int k = L.back();
        L.pop_back();
        if (viz[k] == 0) {
            dfs(k); u++;
        }
    }
    cout << u<<endl;
    for (int i=0;i<u;i++)
    {
        for (int j=0;j<rs[i].size();j++)
        {
            cout << rs[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}