Pagini recente » Cod sursa (job #658704) | Cod sursa (job #894639) | Cod sursa (job #658332) | Cod sursa (job #658703) | Cod sursa (job #3335865)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int E, V, v[100005], cnt;
vector<int> adj[100005], tc[100005], inv[100005];
stack<int> s;
void dfs1(int t){
v[t] = 1;
for(int x : adj[t])
if(!v[x])
dfs1(x);
s.push(t);
}
void dfs2(int t){
v[t] = 1;
tc[cnt].push_back(t);
for(int x : inv[t])
if(!v[x])
dfs2(x);
}
int main(){
f >> V >> E;
for(int i = 1; i <= E; i++){
int x, y;
f >> x >> y;
adj[x].push_back(y);
inv[y].push_back(x);
}
for(int i = 1; i <= V; i++)
if(v[i] == 0)
dfs1(i);
for(int i = 1; i <= V; i++)
v[i] = 0;
while(!s.empty()){
int curr = s.top();
s.pop();
if(v[curr] == 0){
cnt++;
dfs2(curr);
}
}
g << cnt << '\n';
for(int i = 1; i <= cnt; i++, g << '\n'){
sort(tc[i].begin(), tc[i].end());
for(int x : tc[i])
g << x << ' ';
}
}