Cod sursa(job #2632936)

Utilizator marius004scarlat marius marius004 Data 5 iulie 2020 17:44:07
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
// Plus-Minus
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int NMAX = 100'001;
int n, m, p[NMAX], mn[NMAX], cnt;

vector<int> G[NMAX], GT[NMAX];
vector< vector<int> > sol;

void Read() {

    f >> n >> m;

    while(m--) {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void dfs1(int node) {
    p[node] = 1;
    for(int neighbor : G[node])
        if(!p[neighbor])
            dfs1(neighbor);
}

void dfs2(int node) {
    mn[node] = 1;
    for(int neighbor : GT[node])
        if(!mn[neighbor])
            dfs2(neighbor);
}

void restoreArray(int *v,const int& length,const int& value) {
    for(int i = 0;i <= length;++i)
        v[i] = value;
}

void PlusMinus() {

    vector<int> strong_component(n + 1, -1);

    for(int i = 1;i  <= n;++i) {

        if(strong_component[i] == -1) {
            cnt++;
            dfs1(i);
            dfs2(i);
            vector<int> comp;
            for (int node = 1; node <= n; ++node) {
                if (p[node] && mn[node]) {
                    strong_component[node] = cnt;
                    comp.push_back(node);
                }
            }
            sol.push_back(comp);
            restoreArray(p, n, 0);
            restoreArray(mn, n, 0);
        }
    }
}

void Print() {
    g << cnt << '\n';

    for(vector<int> vct : sol) {
        for (int it : vct)
            g << it << ' ';
        g << '\n';
    }
}

int main() {

    Read();
    PlusMinus();
    Print();

    return 0;
}