Pagini recente » Cod sursa (job #2693673) | Cod sursa (job #2533959) | Clasament chestii | Cod sursa (job #1287012) | Cod sursa (job #3230199)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define NMAX 50000
#define NOTVISITED 0
#define VISITING 1
#define VISITED 2
void tarjan(int source, std::vector<int> adj[],
int ×tamp, int found[], int low_link[], int vis[],
std::vector<std::vector<int>> &sccs)
{
++timestamp;
found[source] = timestamp;
low_link[source] = timestamp;
// vis[source] = VISITING;
// sccs.back().push_back(source);
sccs[0].push_back(source);
for (auto neigh : adj[source]) {
// if (vis[neigh] == NOTVISITED) {
if (found[neigh] == -1) {
tarjan(neigh, adj, timestamp, found, low_link, vis, sccs);
low_link[source] = std::min(low_link[source], low_link[neigh]);
}
else if (std::find(sccs[0].begin(), sccs[0].end(), neigh) != sccs[0].end()) {
low_link[source] = std::min(low_link[source], found[neigh]);
}
// else if (vis[neigh] == VISITING) {
// low_link[source] = std::min(low_link[source], found[neigh]);
// }
}
if (low_link[source] == found[source]) {
sccs.push_back({});
// std::cout << "----\n(" << source + 1 << ") - ";
do {
// std::cout << sccs[0].back() + 1 << ' ';
sccs.back().push_back(sccs[0].back());
sccs[0].pop_back();
} while (sccs.back().back() != source);
// std::cout << "\n----\n";
}
// vis[source] = VISITED;
}
int main()
{
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n, m;
std::vector<int> adj[NMAX];
int timestamp = 0, found[NMAX], low_link[NMAX], vis[NMAX];
std::vector<std::vector<int>> sccs;
fin >> n >> m;
for (int v, w, i = 0; i < m; ++i) {
fin >> v >> w;
adj[v - 1].push_back(w - 1);
}
for (int i = 0; i < n; ++i)
// vis[i] = NOTVISITED;
found[i] = -1;
sccs.push_back({});
for (int i = 0; i < n; ++i)
// if (vis[i] == NOTVISITED)
if (found[i] == -1)
tarjan(i, adj, timestamp, found, low_link, vis, sccs);
// sccs.pop_back();
sccs.erase(sccs.begin());
fout << sccs.size() << '\n';
for (auto scc : sccs) {
for (auto node : scc)
fout << node + 1 << ' ';
fout << '\n';
}
// for (int i = 0; i < n; ++i)
// fout << low_link[i] << ' ';
// fout << '\n';
fin.close();
fout.close();
return 0;
}