Cod sursa(job #2107412)

Utilizator felixiPuscasu Felix felixi Data 17 ianuarie 2018 09:55:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

vector<vector<int>> ctc;
vector<pair<int,int>> G[NMAX+2], GP[NMAX+2];
vector<int> order;

bool viz[NMAX+2];
int comp[NMAX+2], profit[NMAX+2], c_ind = 0;
vector<pair<int,int>> NG[NMAX+2];
int N, M;

void Dfs_Plus(int nod)
{
    viz[nod] = 1;
    for( auto e: G[nod] ) {
        int x = e.first;
        if( viz[x] ) continue;
        Dfs_Plus(x);
    }
    order.push_back(nod);
}

void Dfs_Minus(int nod)
{
    comp[nod] = c_ind;
    viz[nod] = 1;

    ctc.back().push_back(nod);

    for( auto e : GP[nod] ) {
        int x = e.first;
        if( viz[x] ) continue;
        Dfs_Minus(x);
    }
}

int main()
{
    in >> N >> M;
    for( int i = 1;  i <= M;  ++i ) {
        int x,y,w;
        in >> x >> y;
        w = 0;
        G[x].push_back({y,w});
        GP[y].push_back({x,w});
    }
    for( int i = 1;  i <= N;  ++i ) {
        if( viz[i] ) continue;
        Dfs_Plus(i);
    }
    memset(viz, 0, sizeof(viz));
    reverse(order.begin(), order.end());
    for( auto x : order ) {
        if( viz[x] ) continue;
        ++c_ind;
        ctc.push_back(vector<int>());
        Dfs_Minus(x);
    }
    ///for( int i = 1;  i <= N;  ++i ) cout << comp[i] << ' ';
    out << ctc.size() << '\n';
    for( auto ln : ctc ) {
        for( auto x : ln ) out << x << ' ';
        out << '\n';
    }
    return 0;
}