Pagini recente » Arhiva de probleme | Cod sursa (job #3233683) | Cod sursa (job #2678085) | Cod sursa (job #1681118) | Cod sursa (job #789344)
Cod sursa(job #789344)
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
#define Max 100000
vector<int>g[Max],t[Max];
deque<deque<int> >d;
deque<int>s;
int n;
bool was[Max],st[Max],dr[Max];
void dfs_st(int x)
{
int y;
st[x]=1;
for(int i=0;i<g[x].size();i++)
{
y=g[x][i];
if(!st[y])dfs_st(y);
}
}
void dfs_dr(int x)
{
int y;
dr[x]=1;
for(int i=0;i<t[x].size();i++)
{
y=t[x][i];
if(!dr[y])dfs_dr(y);
}
}
void ctc()
{
for(int i=1;i<=n;i++)
if(!was[i])
{
memset(st,0,sizeof(st));
memset(dr,0,sizeof(dr));
dfs_st(i);
dfs_dr(i);
s.clear();
for(int j=1;j<=n;j++)
if(st[j] && dr[j])
{
was[j]=1;
s.push_back(j);
}
if(s.size()>0)d.push_back(s);
}
printf("%d\n",d.size());
while(d.size()>0)
{
s=d.front();
d.pop_front();
while(s.size()>0)
{
printf("%d ",s.front());
s.pop_front();
}
printf("\n");
}
}
int main()
{
int m,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
while(m--)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
t[y].push_back(x);
}
ctc();
return 0;
}