Pagini recente » Cod sursa (job #3256729) | Cod sursa (job #98228) | Cod sursa (job #1892834) | Cod sursa (job #55015) | Cod sursa (job #592385)
Cod sursa(job #592385)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define dim 200001
vector <int> v[dim];
vector <int> mat[dim];
vector <int> sol[dim];
//vector <int> lol[dim];
int viz[dim],conex,coada[dim],inc;
bool viz2[dim];
void dfs(int nod)
{
viz[nod]=conex;
coada[++inc]=nod;
for(int i=0;i<v[nod].size();++i)
if(viz[v[nod][i]]==0)
dfs(v[nod][i]);
}
void dfs1(int nod)
{
viz2[nod]=1;
for(int i=0;i<mat[nod].size();++i)
if(viz2[mat[nod][i]]==0)
dfs1(mat[nod][i]);
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, i, j;
fin>>n >>m;
for(i=1;i<=m;++i)
{
fin>>a>>b;
v[a].push_back(b);
mat[b].push_back(a);
}
for(i=1;i<=n;++i)
if(viz[i]==0)
{
inc=0;
++conex;
dfs(i);
dfs1(i);
for(j=1;j<=inc;++j)
{
if(viz[coada[j]]==conex)
if(viz2[coada[j]]==0)
viz[coada[j]]=0;
else
sol[conex].push_back(coada[j]);
//viz2[coada[j]]=0;
}
for(int k=1;k<=n;++k)
viz2[k]=0;
}
fout<<conex<<'\n';
for(i=1;i<=conex;++i)
{
for(j=0;j<sol[i].size();++j)
fout<<sol[i][j]<<" ";
fout<<'\n';
}
return 0;
}