Cod sursa(job #2668218)

Utilizator YesterdayIlie George Ciprian Yesterday Data 4 noiembrie 2020 17:35:21
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include<stdio.h>
#include<vector>

using namespace std;
ifstream f("ctc.in");
ofstream o("ctc.out");
 //implementarea din seminar
#define NMAX 200005

vector<int> ctc[NMAX];
int num_ctc, n, m;
int ctc_of[NMAX], viz[NMAX];
vector<int> graph[NMAX], graph_t[NMAX], ordered_list;

void dfs1(int node) {
    if(viz[node])
        return ;

    viz[node] = 1;
    for(auto vecin : graph[node]) {
        dfs1(vecin);
    }
    ordered_list.push_back(node);
}

void dfs2(int node, int index_ctc) {
    if(ctc_of[node])
        return ;

    ctc_of[node] = index_ctc;
    ctc[index_ctc].push_back(node);

    for(auto vecin : graph_t[node]) {
        dfs2(vecin, index_ctc);
    }
}

int main() {
    int a, b;
    f>>n>>m;
    for(int i = 1; i <= m; i++) {
        f>>a>>b;
        graph[a].push_back(b);
        graph_t[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            dfs1(i);
        }
    }

    for(int i = n - 1; i >= 0; i--) {
        if(!ctc_of[ordered_list[i]]) {
            dfs2(ordered_list[i], ++num_ctc);
        }
    }

   o<<num_ctc<<" ";
    for(int i = 1; i <= num_ctc; i++) {
        for(auto node : ctc[i]) {
            o<<node<<" ";
        }
        o<<endl;
    }

    return 0;
}