Pagini recente » Cod sursa (job #1370779) | Cod sursa (job #3122820) | Cod sursa (job #3154587) | Cod sursa (job #2491462) | Cod sursa (job #2610556)
#include <bits/stdc++.h>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
// Adjacency list for the initial graph
vector<int> adj[kNmax];
// Adjacency list for the transposed graph
vector<int> adj_trans[kNmax];
// scc[i] = strongly connected component with index i
vector<vector<int>> scc;
// visited[i] - 1 - visited node, 0 - node not visited
// DFS on the initial graph -> mark with 1 the nodes
// DFS on the transp graph -> mark with 0 the nodes
vector<int> visited;
// Nodes ascending on finish time
// reverse(topsort) -> the actual topsort
vector<int> topsort;
void read_input() {
ifstream fin("ctc.in");
fin >> n >> m;
visited = vector<int>(n + 1, 0);
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj_trans[y].push_back(x);
}
fin.close();
}
vector<vector<int>> get_result() {
/*
TODO: Gasiti componentele tare conexe ale grafului orientat cu
n noduri, stocat in adj. Rezultatul se va returna sub forma
unui vector, ale carui elemente sunt componentele tare conexe
detectate. Nodurile si componentele tare conexe pot fi puse in orice
ordine in vector.
Atentie: graful transpus este stocat in adjt.
*/
vector<vector<int>> sol;
kosaraju();
sol = scc;
return sol;
}
void kosaraju() {
// Indexing from 1;
topsort.push_back(-1);
// Traverse the initial graph
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i);
}
}
// Traverse the transposed graph generated by
// the topological sort
for (int i = n; i >= 1; --i) {
if (visited[topsort[i]]) { // not visited on the adj_t list
// Build a new scc
vector<int> current_scc;
dfs_t(topsort[i], current_scc);
scc.push_back(current_scc);
}
}
}
// DFS on the normal graph
void dfs(int node) {
visited[node] = 1;
for (auto &ngh : adj[node]) {
if (!visited[ngh]) {
dfs(ngh);
}
}
// Add node to topsort
topsort.push_back(node);
}
// DFS on the transposed graph
void dfs_t(int node, vector<int> ¤t_scc) {
visited[node] = 0;
current_scc.push_back(node);
for (auto &ngh : adj_trans[node]) {
if (visited[ngh]) {
dfs_t(ngh, current_scc);
}
}
}
void print_output(const vector<vector<int>>& result) {
ofstream fout("ctc.out");
fout << result.size() << '\n';
for (const auto& ctc : result) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
// Please always keep this simple main function!
int main() {
// Allocate a Task object on heap in order to be able to
// declare huge static-allocated data structures inside the class.
Task *task = new Task();
task->solve();
delete task;
return 0;
}