Pagini recente » Cod sursa (job #2256908) | Cod sursa (job #1966404) | Cod sursa (job #2459283) | Cod sursa (job #872478) | Cod sursa (job #2668218)
#include <iostream>
#include <fstream>
#include<stdio.h>
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream o("ctc.out");
//implementarea din seminar
#define NMAX 200005
vector<int> ctc[NMAX];
int num_ctc, n, m;
int ctc_of[NMAX], viz[NMAX];
vector<int> graph[NMAX], graph_t[NMAX], ordered_list;
void dfs1(int node) {
if(viz[node])
return ;
viz[node] = 1;
for(auto vecin : graph[node]) {
dfs1(vecin);
}
ordered_list.push_back(node);
}
void dfs2(int node, int index_ctc) {
if(ctc_of[node])
return ;
ctc_of[node] = index_ctc;
ctc[index_ctc].push_back(node);
for(auto vecin : graph_t[node]) {
dfs2(vecin, index_ctc);
}
}
int main() {
int a, b;
f>>n>>m;
for(int i = 1; i <= m; i++) {
f>>a>>b;
graph[a].push_back(b);
graph_t[b].push_back(a);
}
for(int i = 1; i <= n; i++) {
if(!viz[i]) {
dfs1(i);
}
}
for(int i = n - 1; i >= 0; i--) {
if(!ctc_of[ordered_list[i]]) {
dfs2(ordered_list[i], ++num_ctc);
}
}
o<<num_ctc<<" ";
for(int i = 1; i <= num_ctc; i++) {
for(auto node : ctc[i]) {
o<<node<<" ";
}
o<<endl;
}
return 0;
}