Pagini recente » Cod sursa (job #1221250) | Cod sursa (job #903078) | Cod sursa (job #301457) | Cod sursa (job #75467) | Cod sursa (job #2678612)
//
// main.cpp
// ctc
//
// Created by Radu Costache on 28/11/2020.
// Copyright © 2020 Radu Costache. All rights reserved.
//
#include <fstream>
#include <vector>
#include <bitset>
#define NMAX 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, ctc;
vector <int> v1[NMAX];
vector <int> v2[NMAX];
vector <int> ans[NMAX];
void dfs1(int);
void dfs2(int);
bitset <NMAX> viz;
bitset <NMAX> viz1;
bitset <NMAX> viz2;
int main(int argc, const char * argv[]) {
// insert code here...
f >> n;
f >> m;
while (m--) {
int x, y;
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
++ctc;
viz1.reset();
dfs1(i);
viz2.reset();
dfs2(i);
}
}
g << ctc << '\n';
for (int i = 1; i <= ctc; ++i) {
for (auto it:ans[i])
g << it << ' ';
g << '\n';
}
return 0;
}
void dfs1(int node) {
viz1[node] = 1;
for (auto it:v1[node])
if (viz1[it] == 0 && viz[it] == 0) {
dfs1(it);
}
}
void dfs2(int node) {
viz2[node] = 1;
if (viz1[node] == 1) {
ans[ctc].push_back(node);
viz[node] = 1;
}
for (auto it:v2[node])
if (viz2[it] == 0 && viz[it] == 0) {
dfs2(it);
}
}