Pagini recente » Cod sursa (job #2354543) | Cod sursa (job #2186514) | Cod sursa (job #2546056) | Cod sursa (job #103325) | Cod sursa (job #3126976)
#include <bits/stdc++.h>
using namespace std;
class Task {
public:
void solve() {
read_input();
get_result();
print_output();
}
private:
static constexpr int NMAX = (int)1e5 + 5;
int n, m, components;
vector<int> adj[NMAX];
vector<int> new_scc[NMAX];
vector<int> stk;
void read_input() {
ifstream fin("ctc.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
}
fin.close();
}
void DFS(int node, vector<int> &p, int ×tamp, vector<int>& found,
vector<int>& low_link) {
found[node] = ++timestamp;
low_link[node] = found[node];
stk.push_back(node);
for (int neigh : adj[node]) {
if (p[neigh] != -1) {
if (count(stk.begin(), stk.end(), neigh)) {
low_link[node] = min(low_link[node], found[neigh]);
}
continue;
}
p[neigh] = node;
DFS(neigh, p, timestamp, found, low_link);
low_link[node] = min(low_link[node], low_link[neigh]);
}
if (low_link[node] == found[node]) {
int x;
do {
x = stk.back();
stk.pop_back();
new_scc[components].push_back(x);
} while (x != node);
components++;
}
}
void get_result() {
vector<int> found(n + 1);
vector<int> p (n + 1);
vector<int> low_link(n + 1);
components = 0;
for (int i = 1; i <= n; i++) {
p[i] = -1;
}
for (int i = 1; i <= n; i++) {
found[i] = NMAX;
low_link[i] = NMAX;
}
int timestamp = 0;
for (int i = 1; i <= n; i++) {
if (p[i] == -1) {
p[i] = i;
DFS(i, p, timestamp, found, low_link);
}
}
}
void print_output() {
ofstream fout("ctc.out");
fout << components << endl;
for (int i = 0; i <= components; i++) {
for (int j = 0; j < new_scc[i].size(); j++) {
fout << new_scc[i][j] << " ";
}
fout << endl;
}
fout.close();
}
};
int main() {
auto* task = new (nothrow) Task();
if (!task) {
cerr << "new failed: WTF are you doing? Throw your PC!\n";
return -1;
}
task->solve();
delete task;
return 0;
}