Cod sursa(job #2724376)

Utilizator matei8787Matei Dobrea matei8787 Data 16 martie 2021 23:20:03
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> graf[100005];
vector<int> frateleGay[100005];
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m;
void makeFrateleGay()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        for ( int j = 0 ; j < graf[i].size() ; j++ )
        {
            frateleGay[graf[i][j]].pb(i);
        }
    }
}
void citire()
{
    in>>n>>m;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x,y;
        in>>x>>y;
        graf[x].pb(y);
    }
}
int vc[100005];
int vc1[100005];
int vc2[100005];
void reface()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        vc1[i] = vc2[i] = vc[i];
    }
}
void dfsGraf(int nod)
{
    vc1[nod] = 1;
    for ( int i = 0 ; i < graf[nod].size() ; i++ )
    {
        if ( vc1[graf[nod][i]] == 0 )
        {
            dfsGraf(graf[nod][i]);
        }
    }
}
void dfsGay(int nod)
{
    vc2[nod] = 1;
    for ( int i = 0 ; i < frateleGay[nod].size() ; i++ )
    {
        if ( vc2[frateleGay[nod][i]] == 0 )
        {
            dfsGay(frateleGay[nod][i]);
        }
    }
}
void scoateNod(int nod)
{
    vc[nod] = -1;
}
vector<int> careAmbele ()
{
    vector<int> ans;
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( vc1[i] == 1 && vc2[i] == 1 )
        {
            ans.pb(i);
            scoateNod(i);
        }
    }
    return ans;
}
bool areNodes()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( vc[i] == 0 )
            return true;
    }
    return false;
}
int primulNodNeluat()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( vc[i] == 0 ){
            return i;
        }
    }
    return -1;
}
void rez()
{
    vector<vector<int>> ans;
    while ( areNodes() == true )
    {
        int aux = primulNodNeluat();
        dfsGraf(aux);
        dfsGay(aux);
        ans.pb(careAmbele());
        reface();
    }
    out<<ans.size()<<'\n';
    for ( int i = 0 ; i < ans.size() ; i++ )
    {
        for ( int j = 0 ; j < ans[i].size() ; j++ )
        {
            out<<ans[i][j]<<" ";
        }
        out<<'\n';
    }
}
int main()
{
    citire();
    makeFrateleGay();
    rez();
    return 0;
}