Pagini recente » Cod sursa (job #831013) | Cod sursa (job #2558474) | Cod sursa (job #919177) | Cod sursa (job #1781516) | Cod sursa (job #2724594)
#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;
}