Pagini recente » Cod sursa (job #2272477) | Cod sursa (job #795470) | Cod sursa (job #2184836) | Cod sursa (job #2890998) | Cod sursa (job #3269143)
#include <bits/stdc++.h>
using namespace std;
#define TITLE "ctc"
ifstream f (TITLE".in");
ofstream g (TITLE".out");
int n,m;
bitset<100002> Visited;
int Topologic[100002],temp;
void TopDfs(int Node, vector<vector<int>> &Graph)
{
Visited[Node]=true;
for(auto it : Graph[Node])
if(!Visited[it])
TopDfs(it,Graph);
Topologic[++temp]=Node;
}
void Dfs(int Node, vector<vector<int>> &Graph, vector<int> &Answer)
{
Visited[Node]=true;
Answer.push_back(Node);
for(auto it : Graph[Node])
if(!Visited[it])
Dfs(it,Graph,Answer);
}
int main()
{
f>>n>>m;
vector<vector<int>> Graph(n+1),TGraph(n+1);
while(m--)
{
int a,b;
f>>a>>b;
Graph[a].push_back(b);
TGraph[b].push_back(a);
}
for(int i=1; i<=n; i++)
if(!Visited[i])
TopDfs(i,Graph);
Visited=0;
vector<vector<int>>Answer;
for(int i=n; i; i--)
if(!Visited[Topologic[i]])
{
Answer.push_back(vector<int>());
Dfs(Topologic[i],TGraph,Answer[Answer.size()-1]);
}
g<<Answer.size()<<'\n';
for(auto it : Answer)
{
for(auto it2 : it)
g<<it2<<' ';
g<<'\n';
}
return 0;
}