Pagini recente » Cod sursa (job #2551779) | Cod sursa (job #456528) | Cod sursa (job #2584796) | Cod sursa (job #2337586) | Cod sursa (job #846481)
Cod sursa(job #846481)
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
#define Max 100001
vector<int>g[Max],t[Max],c;
vector<vector<int> >d;
bool viz[Max],gviz[Max],tviz[Max];
int n;
void dfs(int x,vector<int>g[],bool viz[])
{
int y;
viz[x]=1;
for(int i=0;i<g[x].size();i++)
{
y=g[x][i];
if(!viz[y])dfs(y,g,viz);
}
}
void ctc()
{
int nr=0;
for(int i=1;i<=n;i++)
if(!viz[i])
{
memset(gviz,0,sizeof(gviz));
memset(tviz,0,sizeof(tviz));
dfs(i,g,gviz);
dfs(i,t,tviz);
nr++;
for(int i=1;i<=n;i++)
if(gviz[i] && tviz[i])
{
viz[i]=1;
c.push_back(i);
}
d.push_back(c);
c.resize(0);
}
printf("%d\n",nr);
for(int i=0;i<d.size();i++)
{
for(int j=0;j<d[i].size();j++)printf("%d ",d[i][j]);
printf("\n");
}
}
int main()
{
int m,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
t[y].push_back(x);
}
ctc();
return 0;
}