Pagini recente » Clasament simulare_oji_2023_clasa_9_10_martie | Cod sursa (job #109550) | Cod sursa (job #2137799) | Cod sursa (job #1629200) | Cod sursa (job #2724376)
#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;
}