Cod sursa(job #2724594)

Utilizator matei8787Matei Dobrea matei8787 Data 17 martie 2021 13:42:13
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 kb
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m;
struct Graf
{
    int componenta;
    vector<int> catre;
};
Graf graf[100005];
Graf frateleGay[100005];
void citire()
{
    in>>n>>m;
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x,y;
        in>>x>>y;
        graf[x].catre.pb(y);
    }
}
void makeFrateleGay()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        for ( int j = 0 ; j < graf[i].catre.size() ; j++ )
        {
            frateleGay[graf[i].catre[j]].catre.pb(i);
        }
    }
}
set<int> noduriGraf;
set<int> noduriGay;
void dfsGraf(int nod)
{
    noduriGraf.insert(nod);
    for ( int i = 0 ; i < graf[nod].catre.size() ; i++ )
    {
        if ( graf[graf[nod].catre[i]].componenta == 0 && noduriGraf.find(graf[nod].catre[i]) == noduriGraf.end() )
        {
            dfsGraf(graf[nod].catre[i]);
        }
    }
}
void dfsGay(int nod)
{
    noduriGay.insert(nod);
    for ( int i = 0 ; i < frateleGay[nod].catre.size() ; i++ )
    {
        if ( frateleGay[frateleGay[nod].catre[i]].componenta == 0 && noduriGay.find(frateleGay[nod].catre[i]) == noduriGay.end() )
        {
            dfsGay(frateleGay[nod].catre[i]);
        }
    }
}
vector<vector<int>> ans;
void makeTariConexe( int k )
{
    ans.resize(ans.size() + 1);
    for ( auto i = noduriGraf.begin() ; i != noduriGraf.end() ; i++ )
    {
        if ( noduriGay.find(*i) != noduriGay.end() )
        {
            graf[*i].componenta = k;
            frateleGay[*i].componenta = k;
            ans[ans.size()-1].pb(*i);
        }
    }
    noduriGay.erase(noduriGay.begin(),noduriGay.end());
    noduriGraf.erase(noduriGraf.begin(),noduriGraf.end());
}
int primulNodNefacut()
{
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( graf[i].componenta == 0 )
            return i;
    }
    return -1;
}
void rez()
{
    int aux = primulNodNefacut();
    int k = 1;
    while ( aux != -1 )
    {
        dfsGraf(aux);
        dfsGay(aux);
        makeTariConexe(k++);
        aux = primulNodNefacut();
    }
    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;
}