Pagini recente » Cod sursa (job #618902) | Cod sursa (job #1857272) | Cod sursa (job #471460) | Cod sursa (job #1578674) | Cod sursa (job #1801683)
#include <iostream>
#include <fstream>
#include <vector>
#define infile "ctc.in"
#define outfile "ctc.out"
using namespace std;
ifstream in(infile);
ofstream out(outfile);
int n, m;
int x, y;
vector<int> graph[100005];
vector<int> graphT[100005];
vector<int> component[100005];
bool vis[100005];
vector<int> discovered;
int roots[100005];
vector<int> nodes;
int count;
void firstDFS(int node)
{
vis[node] = true;
for(vector<int> :: iterator it=graph[node].begin(); it!=graph[node].end(); it++){
if(!vis[*it]){
firstDFS(*it);
}
}
discovered.push_back(node);
}
void secondDFS(int node, int root)
{
roots[node] = root;
nodes.push_back(node);
for(vector<int> :: iterator it=graphT[node].begin(); it!=graphT[node].end(); it++){
if(!roots[*it]){
secondDFS(*it, root);
}
}
}
int main()
{
in >> n >> m;
for(int i=0; i<m; i++){
in >> x >> y;
graph[x].push_back(y);
graphT[y].push_back(x);
}
for(int i=1; i<=n; i++){
if(!vis[i]){
firstDFS(i);
}
}
for(; discovered.size(); discovered.pop_back()){
if(!roots[discovered.back()]){
count++;
secondDFS(discovered.back(), count);
}
}
for(int i=1; i<=n; i++){
component[roots[i]].push_back(i);
}
out << count << '\n';
for(int i=1; i<=count; i++){
for(vector<int> :: iterator it=component[i].begin(); it!=component[i].end(); it++){
out << *it << ' ';
}
out << '\n';
}
return 0;
}