Pagini recente » Cod sursa (job #2455904) | Cod sursa (job #473710) | Cod sursa (job #895361) | Cod sursa (job #110214) | Cod sursa (job #717075)
Cod sursa(job #717075)
#include<fstream>
#include<vector>
#include<algorithm>
#define dim 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int> > mat(dim);
vector<vector<int> > matt(dim);
vector<int> viz(dim);
vector<int> vizt(dim);
int n,m,i,j,x,y,conex;
inline void df(int x)
{
viz[x]=conex;
for(int i=0;i<mat[x].size();++i)
if(!viz[mat[x][i]])
df(mat[x][i]);
}
inline void dft(int x)
{
vizt[x]=conex;
for(int i=0;i<matt[x].size();++i)
if(!vizt[matt[x][i]])
dft(matt[x][i]);
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
mat[x].push_back(y);
matt[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!viz[i] && !vizt[i])
{
++conex;
df(i);
dft(i);
for(j=1;j<=n;++j)
viz[j]=vizt[j]=min(viz[j],vizt[j]);
}
g<<conex<<"\n";
for(i=1;i<=conex;++i)
{
for(j=1;j<=n;++j)
if(viz[j]==i)
g<<j<<" ";
g<<"\n";
}
return 0;
}