Cod sursa(job #2974517)

Utilizator ioana.cCaprariu Ioana ioana.c Data 4 februarie 2023 10:05:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
//kosaraju
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100010

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, vis1[nmax], vis2[nmax], c1, c2;

vector <int> g[nmax];
vector <int> gt[nmax];
vector <vector<int>> ctc;
stack <int> s;

void dfs1(int i){
    vis1[i] = c1;
    for(auto j : g[i])
        if(!vis1[j])
            dfs1(j);
    s.push(i);
}

void dfs2(int i){
    vis2[i] = c2;
    for(auto j : gt[i])
        if(!vis2[j])
            dfs2(j);
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++){
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!vis1[i]){
            c1++;
            dfs1(i);
        }
    while(!s.empty()){
        int x=s.top();
        s.pop();
        if(!vis2[x]){
            c2++;
            dfs2(x);
        }
    }
    ctc.clear();
    ctc.resize(c2);
    for(int i=1; i<=n; i++)
        ctc[vis2[i]-1].push_back(i);
    fout << ctc.size() << '\n';
    for(auto &i : ctc){
        for(auto &j : i)
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}