Pagini recente » Cod sursa (job #2924326) | Cod sursa (job #3002003) | Cod sursa (job #642371) | Cod sursa (job #916080) | Cod sursa (job #1547699)
#include <stdio.h>
#include <vector>
#include <stack>
#define maxn 100005
using namespace std;
vector <int> a[maxn],atr[maxn],cc[maxn];
stack <int> s;
bool viz[maxn];
int n,m;
void dfs(int nod, bool (&viz)[maxn])
{
viz[nod]=1;
unsigned int i;
for(i=0; i<a[nod].size(); i++)
if(viz[a[nod][i]] == 0) dfs(a[nod][i], viz);
s.push(nod);
}
void dfs2(int nod, bool (&viz)[maxn], int &nrc)
{
viz[nod]=0;
unsigned int i;
for(i=0; i<atr[nod].size(); i++)
if(viz[atr[nod][i]] == 1) dfs2(atr[nod][i], viz, nrc);
cc[nrc].push_back(nod);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
int i,x,y;
for(i=0; i<m; i++)
{
scanf("%d %d",&x,&y);
a[x].push_back(y);
atr[y].push_back(x);
}
for(i=1; i<=n; i++)
if(viz[i] == 0)
dfs(i, viz);
int nrc = 0;
while(!s.empty())
{
x = s.top();
s.pop();
if (viz[x] != 0)
{
dfs2(x, viz, nrc);
nrc++;
}
}
printf("%d\n",nrc);
for(i=0; i<nrc; i++)
{
unsigned int j;
for(j=0; j<cc[i].size(); j++)
printf("%d ",cc[i][j]);
printf("\n");
}
return 0;
}