Pagini recente » Cod sursa (job #1001023) | Cod sursa (job #1725399) | Cod sursa (job #1701488) | Cod sursa (job #1087933) | Cod sursa (job #744375)
Cod sursa(job #744375)
#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>
#define NN 100001
#define pb push_back
using namespace std;
ofstream out("ctc.out");
vector<int>G1[NN];
vector<int>G2[NN];
typedef vector<int>:: iterator IT;
int n,m,v1[NN],v2[NN],c[NN];
void citire()
{
ifstream in("ctc.in");
in>>n>>m;
int i,j;
for(;m;--m)
{
in>>i>>j;
G1[i].pb(j);
G2[j].pb(i);
}
}
void DFS(vector<int>*g,int start ,int n ,int v[100])
{
v[start]=1;
for(vector<int>::iterator i=g[start].begin();i<g[start].end();++i)
if(!v[*i])
DFS(g,*i,n,v);
}
void rez(int vf,int ctc)
{
memset(v1,0,sizeof(v1));
memset(v2,0,sizeof(v2));
DFS(G1,vf,n,v1);
DFS(G2,vf,n,v2);
for(int i=1;i<=n;i++)
if(v1[i]==v2[i]&&v1[i]!=0)
c[i]=ctc;
}
int main()
{
citire();
int nrc=0;
for(int i=1;i<=n;i++)
if(c[i]==0)
{
++nrc;
rez(i,nrc);
}
out<<nrc<<'\n';
for(int i=1;i<=nrc;i++)
{
for(int j=1;j<=n;j++)
if(c[j]==i)
out<<j<<" ";
out<<'\n';
}
return 0;
}