Cod sursa(job #2224621)

Utilizator stefan.botezStefan Botez stefan.botez Data 24 iulie 2018 17:32:32
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <stack>
#include <deque>

using namespace std;

const int nmax = 100005;

int n, m, x, y, id, cnt, ids[nmax], low[nmax];
vector<int> v[nmax], comp[nmax];
bitset<nmax> viz;
deque<int> s;

void dfs(int a)
{
    s.push_front(a);
    cout << s.front() << endl;
    viz[a] = true;
    ids[a] = low[a] = id++;

    for(auto it : v[a])
    {
        if(ids[it] == -1) dfs(it);
        if(viz[it] == true) low[a] = min(low[a], low[it]);
    }

    if(low[a] == ids[a])
    {
        for(int node = s.front();cnt!=-1 ; node = s.front())
        {
            comp[cnt].push_back(node);
            s.pop_front();
            viz[node] = false;
            low[node] = ids[a];
            if(node == a)break;
        }
        cnt++;
    }
}

int main()
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y;
        v[x-1].push_back(y-1);
    }
    for(int i = 0; i < n; i++)
        ids[i] = -1;
    for(int i = 0; i < n; i++)
        if(ids[i] == -1)
            dfs(i);
    g<<cnt<<endl;
    for(int i = 0; i < cnt; i++)
    {
        for(auto it : comp[i])
            g<<it + 1<<" ";
        g<<endl;
    }
    return 0;
}