Pagini recente » Cod sursa (job #1867865) | Cod sursa (job #2453786) | Cod sursa (job #839155) | Cod sursa (job #3153759) | Cod sursa (job #2481739)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> Gi[100005];
vector <int> Go[100005];
int n, m;
bool visited[100005];
vector<int> discovered;
int where[100005];
int comp;
void citire() {
f >> n >> m;
for(int i = 0; i < m; i++) {
int x, y;
f >> x >> y;
Go[x].push_back(y);
Gi[y].push_back(x);
}
}
void dfs(int x) {
visited[x] = true;
for(int i = 0; i < Go[x].size(); i++) {
int y = Go[x][i];
if(!visited[y])
dfs(y);
}
discovered.push_back(x);
}
void Assign(int x, int root) {
where[x] = root;
for(int i = 0; i < Gi[x].size(); i++) {
int y = Gi[x][i];
if(where[y] == -1)
Assign(y, root);
}
}
void afis() {
g << comp << '\n';
for(int nr = 0; nr < comp; nr++) {
for(int i = 1; i <= n; i++)
if(where[i] == nr)
g << i << ' ';
g << '\n';
}
}
int main() {
citire();
for(int i = 1; i <= n; i++)
if(!visited[i])
dfs(i);
memset(where, -1, sizeof where);
for( ;discovered.size(); discovered.pop_back()) {
int b = discovered[discovered.size()-1];
if(where[b] == -1) {
Assign(b, comp);
comp++;
}
}
afis();
}