Cod sursa(job #2529696)

Utilizator PaterucAPetruc Andrei Stefan PaterucA Data 23 ianuarie 2020 20:36:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

ifstream inf("ctc.in");
ofstream outf("ctc.out");

const int N=100010;

int n, m, sol;
vector<int> v[N], w[N];
vector<int> ctc[N];
stack<int> s;
bitset<N> vis;

void dfs(int ), dfsUtil(int );

int main()
{
    inf>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        inf>>x>>y;
        v[x].push_back(y);
        w[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])
            dfs(i);
    vis.reset();
    while(!s.empty())
    {
        int x=s.top();
        s.pop();
        if(!vis[x])
            sol++,dfsUtil(x);
    }
    outf<<sol<<'\n';
    for(int i=1; i<=sol; i++)
    {
        for(auto it:ctc[i])
            outf<<it<<' ';
        outf<<'\n';
    }
    return 0;
}

void dfs(int nod)
{
    vis[nod]=1;
    for(auto it:v[nod])
    {
        if(!vis[it])
            dfs(it);
    }
    s.push(nod);
}

void dfsUtil(int nod)
{
    vis[nod]=1;
    ctc[sol].push_back(nod);
    for(auto it:w[nod])
    {
        if(!vis[it])
            dfsUtil(it);
    }
}