Pagini recente » Cod sursa (job #177837) | Cod sursa (job #2885408) | Cod sursa (job #1951585) | Cod sursa (job #1585200) | Cod sursa (job #1686975)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 100005;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <int> G[MaxN], Gt[MaxN], Comp[MaxN], comp_order;
bool used[MaxN];
int n, m, CompNr;
void Dfs(int node) {
used[node] = true;
for(auto nxt: G[node]) {
if(used[nxt]) {
continue;
}
Dfs(nxt);
}
comp_order.push_back(node);
}
void DfsT(int node, int curr_comp) {
used[node] = true;
Comp[curr_comp].push_back(node);
for(auto nxt: Gt[node]) {
if(used[nxt]) {
continue;
}
DfsT(nxt, curr_comp);
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for(int i = 1; i <= n; ++i) {
if(used[i]) {
continue;
}
Dfs(i);
}
memset(used, 0, sizeof used);
reverse(comp_order.begin(), comp_order.end());
for(auto it: comp_order) {
if(used[it]) {
continue;
}
++CompNr;
DfsT(it, CompNr);
}
cout << CompNr << '\n';
for(int i = 1; i <= CompNr; ++i) {
for(auto it: Comp[i]) {
cout << it << ' ';
}
cout << '\n';
}
return 0;
}
/*#include <fstream>
#include <vector>
using namespace std;
const int MaxN = 100005;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <int> G[MaxN], StrongCom, partial_ans;
vector <vector <int>> Ans;
int depth[MaxN], highest[MaxN], UseRmv[MaxN];
int n, m, level;
void BuildStrongComp(int end_node) {
int curr_node;
do {
curr_node = StrongCom.back();
StrongCom.pop_back();
partial_ans.push_back(curr_node);
UseRmv[curr_node] = 2;
} while(!StrongCom.empty() and curr_node != end_node);
Ans.push_back(partial_ans);
partial_ans.clear();
}
void Dfs(int node = 1) {
UseRmv[node] = 1;
depth[node] = ++level;
highest[node] = level;
StrongCom.push_back(node);
for(auto nxt: G[node]) {
if(UseRmv[nxt] == 0) {
Dfs(nxt);
highest[node] = min(highest[node], highest[nxt]);
}
else if(UseRmv[nxt] == 1) {
highest[node] = min(highest[node], highest[nxt]);
}
}
if(highest[node] == depth[node]) {
BuildStrongComp(node);
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
for(int i = 1; i <= n; ++i) {
if(UseRmv[i]) {
continue;
}
Dfs(i);
}
cout << Ans.size() << '\n';
for(auto ans: Ans) {
for(auto it: ans) {
cout << it << ' ';
}
cout << '\n';
}
return 0;
}
*/