Pagini recente » Cod sursa (job #2748027) | Cod sursa (job #2740305) | Cod sursa (job #1101226) | Cod sursa (job #725626) | Cod sursa (job #3040240)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 1e5;
vector<int> v[N + 1] , v1[N + 1] , ctc[N + 1]; // v -> succesori , v1 -> pred
stack<int> s;
int sort_t[N + 1] , visited[N + 1] , nr_ord_c[N + 1] , n , m , nr;
void dfs(int i){
visited[i] = true;
for(int y = 0 ; y < v[i].size() ; y++){
int val = v[i][y];
if(!visited[val]){
dfs(val);
}
}
s.push(i);
}
void dfs_invers(int i , int nr_ord){
nr_ord_c[i] = nr_ord;
for(int y = 0 ; y < v1[i].size() ; y++){
int val = v1[i][y];
if(!nr_ord_c[val]){
dfs_invers(val , nr_ord);
}
}
}
int main(){
in >> n >> m;
for(int i = 1 ; i <= m ; ++i){
int x , y;
in >> x >> y;
v[x].push_back(y);
v1[y].push_back(x);
}
for(int i = 1 ; i <= n ; i++){
if(!visited[i]){
dfs(i);
}
}
while(!s.empty()){
int x = s.top();
s.pop();
if(nr_ord_c[x] == 0){
dfs_invers(x , ++nr);
}
}
int maxi = -1;
for(int i = 1 ; i <= n ; i++){
maxi = max(maxi , nr_ord_c[i]);
ctc[nr_ord_c[i]].push_back(i);
}
out << maxi << '\n';
for(int i = 1 ; i <= maxi ; i++){
for(int y = 0 ; y < ctc[i].size() ; ++y){
out << ctc[i][y] << ' ';
}
out << '\n';
}
}