Cod sursa(job #2778079)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 28 septembrie 2021 11:35:52
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std ;

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

int n ;

int verif[100009] ;

int paths[109][109] ;

vector<int> m[100009] ;

void fil(int nod, int acata)
{
    verif[nod] = 1 ;

    paths[nod][acata] = acata ;

    for(int f = 0 ; f < m[nod].size() ; f ++)
        if(!verif[m[nod][f]])fil(m[nod][f], acata) ;
}

vector<int> curenta ;

int deja_adaugat[109] ;

bool adauga_noduri()
{

    /// incearca fiecare nod care nu este deja adaugat

    for(int f = 1 ; f <= n ; f ++)
        if(!deja_adaugat[f])
        {

            /// verificam daca putem duce path de la el la orice altii si de la orice altii la el

            int ok = 1 ;

            for(int e = 0 ; e < curenta.size() ; e ++)
                if(!paths[curenta[e]][f] || !paths[f][curenta[e]])
                    ok = 0 ;

            if(ok)curenta.push_back(f), deja_adaugat[f] = 1 ;
        }

}

int main()
{
    int q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b ;

        cin >> a >> b ;

        m[a].push_back(b) ;
    }

    for(int f = 1 ; f <= n ; f ++)
    {

        fil(f, f) ;

        for(int e = 1 ; e <= n ; e ++)
            verif[e] = 0 ;

    }

    int rez = 0 ;

    vector<vector<int> > fin ;

    for(int f = 1 ; f <= n ; f ++)
    {

        curenta.push_back(f) ;

        deja_adaugat[f] = 1 ;

        adauga_noduri() ;

        if(curenta.size() >= 2)rez ++, fin.push_back(curenta) ;

        curenta.clear() ;

    }

    cout << rez << endl ;

    for(int f = 0 ; f < fin.size() ; f ++)
    {

        for(int e = 0 ; e < fin[f].size() ; e ++)
            cout << fin[f][e] << " " ;

        cout << '\n' ;

    }

    return 0 ;
}