Pagini recente » Cod sursa (job #3125851) | Cod sursa (job #895216) | Cod sursa (job #539609) | Cod sursa (job #2642587) | Cod sursa (job #2796417)
#include <fstream>
#include <vector>
#define N_MAX 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,k,nr;
vector<vector<int>> a(N_MAX);
vector<vector<int>> b(N_MAX);
vector<int> viz1(N_MAX),viz2(N_MAX),v(N_MAX);
vector<vector<int>> afis(N_MAX);
void citire()
{
int x,y;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
a[x].push_back(y);
b[y].push_back(x);
}
}
void df(int x)
{
viz1[x]=1;
for(int i : a[x])
if(viz1[i]==0 )
df(i);
}
void revdf(int x)
{
viz2[x]=2;
for(int i : b[x])
if(viz2[i]==0 )
revdf(i);
}
void tareconex()
{
int i,j;
for(i=1;i<=n;i++)
if(viz1[i]==0 && viz2[i]==0)
{
k++;
df(i);
revdf(i);
for(j=1;j<=n;j++)
if(viz1[j]==1 && viz2[j]==2 && v[j]==0)
{
afis[nr].push_back(j);
v[j]=k;
}
else
if((viz1[j]!=1 || viz2[j]!=2) && v[j]==0)
viz1[j]=viz2[j]=0;
nr++;
}
}
int main()
{
citire();
tareconex();
g<<nr;
g<<'\n';
for(auto x :afis)
{for(int y : x)
g<<y<<" ";
g<<'\n';
}
return 0;
}