Pagini recente » Cod sursa (job #1794006) | Cod sursa (job #2293977) | Cod sursa (job #946685) | Cod sursa (job #1621233) | Cod sursa (job #715265)
Cod sursa(job #715265)
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
#define NN 100001
using namespace std;
ofstream out("ctc.out");
vector<vector<int> >G;
vector<vector<int> >G1;
int v1[NN],v2[NN],n,m,rez;
void citire();
void dfs1(int,int);
void dfs2(int,int);
int main()
{
citire();
for(int i=1;i<=n;i++)
if(!v1[i]&&!v2[i])
{
++rez;
dfs1(i,rez);
dfs2(i,rez);
for(int j=1;j<=n;j++)
v1[j]=v2[j]=min(v1[j],v2[j]);
}
out<<rez<<'\n';
for(int j=1;j<=rez;j++)
{
for(int i=1;i<=n;i++)
if(v1[i]==j)
out<<i<<" ";
out<<'\n';
}
return 0;
}
void dfs1(int x,int cul)
{
v1[x]=cul;
for(vector<int>::iterator i=G[x].begin();i<G[x].end();++i)
if(!v1[*i])
dfs1(*i,cul);
}
void dfs2(int x,int cul)
{
v2[x]=cul;
for(vector<int>::iterator i=G1[x].begin();i<G1[x].end();++i)
if(!v2[*i])
dfs2(*i,cul);
}
void citire()
{
ifstream in("ctc.in");
in>>n>>m;
G.resize(n+1);
G1.resize(n+1);
for(int x,y;m;--m)
{
in>>x>>y;
G[x].pb(y);
G1[y].pb(x);
}
}