Pagini recente » Cod sursa (job #2622778) | Cod sursa (job #573475) | Cod sursa (job #3139130) | Cod sursa (job #2096793) | Cod sursa (job #1850793)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <unordered_map>
using namespace std;
#define NMAX 100001
bitset<NMAX>visited;
vector<int>graph[NMAX], grapht[NMAX];
int n,m;
stack<int>vstack;
unordered_map<int,vector<int> >components;
vector<int> roots;
void read()
{
scanf("%d %d ",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d ",&x,&y);
graph[x].push_back(y);
grapht[y].push_back(x);
}
}
void dfs(int node)
{
visited[node]=1;
for(vector<int>::iterator it = graph[node].begin(); it!= graph[node].end(); ++it)
{
if(!visited[*it])
dfs(*it);
}
vstack.push(node);
}
void dfs1(int u,int root)
{
components[root].push_back(u);
visited[u]=1;
for(vector<int>::iterator it = grapht[u].begin(); it!= grapht[u].end(); ++it)
{
if(!visited[*it])
dfs1(*it,root);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
for(int i=1;i<=n;i++)
{
if(!visited[i])
{
dfs(i);
}
}
visited.reset();
while(!vstack.empty())
{
int node = vstack.top();
if(!visited[node])
{
visited[node]=1;
roots.push_back(node);
dfs1(node,node);
}
vstack.pop();
}
int number = components.size();
printf("%d\n",number);
for(int i=1;i<=number;i++)
{
int root = roots[i-1];
int number1 = components[root].size();
for(int j=0;j<number1;j++)
printf("%d ",components[root][j]);
printf("\n");
}
return 0;
}