Cod sursa(job #2604044)

Utilizator Cristian25Cristian Stanciu Cristian25 Data 21 aprilie 2020 15:41:16
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <vector>
#include <stdio.h>
#define pb push_back
#define NMAX 100001

using namespace std;

vector<unsigned> v[NMAX], comp;
vector<bool> viz;

unsigned N, M, cont;
bool conect;

void dfs2(unsigned src, unsigned dest)
{
    viz[src] = true;
    for(unsigned i = 0; i < v[src].size() && !conect; ++i)
        if(v[src][i] == dest)
        {
            conect = true;
            return;
        }
        else if(!viz[v[src][i]])
            dfs2(v[src][i], dest);
}

void reset()
{
    for(unsigned i = 1; i <= N; viz[i++] = false);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    cin >> N >> M;
    for(unsigned i = 1; i <= M; ++i)
    {
        unsigned x, y;
        cin >> x >> y;
        v[x].pb(y);
    }
    fclose(stdin);
    comp.resize(N + 1);
    viz.resize(N + 1);
    reset();
    vector<unsigned> c[NMAX];
    for(unsigned i = 1; i <= N; ++i)
    {
        bool gasit = false;
        for(unsigned j = 1; j < i; ++j)
        {
            conect = false;
            dfs2(i, j);
            reset();
            if(!conect)
                continue;
            conect = false;
            dfs2(j, i);
            reset();
            if(conect)
            {
                c[comp[j]].pb(i);
                comp[i] = comp[j];
                gasit = true;
                break;
            }
        }
        if(!gasit)
        {
            comp[i] = ++cont;
            c[cont].pb(i);
        }
    }
    freopen("ctc.out", "w", stdout);
    cout << cont;
    for(unsigned i = 1; i <= cont; ++i)
    {
        cout << endl;
        for(auto k : c[i])
            cout << k << ' ';
    }
    fclose(stdout);
    return 0;
}