Cod sursa(job #1919388)

Utilizator KimerthSilviu Motfolea Kimerth Data 9 martie 2017 19:10:38
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define MAX_SIZE 100000

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

vector<int> G[MAX_SIZE];
stack<int> S;
vector<vector<int>> SOLUTIONS;
int index;

void strongconnect(int v)
{
    G[v][0] = index;
    G[v][1] = index;
    index++;
    S.push(v);
    G[v][2] = 1;

    for(int i = 3; i < G[v].size(); i++)
    {
        if(G[G[v][i]][0] == -1)
        {
            strongconnect(G[v][i]);
            G[v][1] = min(G[v][1], G[G[v][i]][1]);
        }
        else if(G[G[v][i]][2] == 1)
        {
            G[v][1] = min(G[v][1], G[G[v][i]][1]);
        }
    }

    if(G[v][1] == G[v][0])
    {
        vector<int> sol;
        int w;
        do
        {
            w = S.top();
            S.pop();
            G[w][2] = 0;
            sol.push_back(w);
        }while(w != v);
        SOLUTIONS.push_back(sol);
    }
}

int main()
{
    int n,m;
    fin >> n >> m;

    for(int i = 0; i < n; i++)
    {
        G[i].push_back(-1);
        G[i].push_back(-1);
        G[i].push_back(0);
    }

    for(int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;

        G[x- 1].push_back(y - 1);
    }

    for(int i = 0; i < n; i++)
        if(G[i][0] == -1)
            strongconnect(i);

    fout << SOLUTIONS.size() << '\n';
    for(int i = 0; i < SOLUTIONS.size(); i++)
    {
        for(int j = 0; j < SOLUTIONS[i].size(); j++)
            fout << SOLUTIONS[i][j] + 1 << ' ';
        fout << '\n';
    }


    return 0;
}