Cod sursa(job #2632938)

Utilizator marius004scarlat marius marius004 Data 5 iulie 2020 17:47:56
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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< int > sol[NMAX];

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 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 = i; node <= n; ++node) {
                if (p[node] && mn[node]) {
                    strong_component[node] = cnt;
                    sol[cnt].push_back(node);
                }
            }
            
            for(int i = 1;i <= n;++i)
                p[i] = mn[i] = 0;
        }
    }
}

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

    for(int i = 1;i <= cnt;++i, g << '\n' )
        for(int it : sol[i])
            g << it << ' ';
}

int main() {

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

    return 0;
}