Pagini recente » Cod sursa (job #2265520) | Cod sursa (job #1964706) | Cod sursa (job #727024) | Cod sursa (job #1252686) | Cod sursa (job #2795722)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
class Graph {
public:
// dfs
void DFS(int v, vector<bool> &vis) {
vis[v] = true;
for (auto &x : m_ad[v]) {
if (!vis[x]) {
DFS(x, vis);
}
}
}
int components() {
int compCount = 0;
vector<bool> vis(m_n, false);
for (int i = 1; i <= m_n; ++i) {
if (!vis[i]) {
++compCount;
DFS(i, vis);
}
}
return compCount;
}
// bfs
void minDist(int start) {
vector<int> dist(m_n + 1, -1);
queue<int> Q;
int x;
dist[start] = 0;
Q.push(start);
while (!Q.empty()) {
x = Q.front(); Q.pop();
for (auto &y : m_ad[x]) {
if (dist[y] == -1) {
dist[y] = dist[x] + 1;
Q.push(y);
}
}
}
for (int i = 1; i <= m_n; ++i) {
fout << dist[i] << ' ';
}
}
// ctc
void topologicalSort(int v, vector<bool> &vis, vector<int> &stack) {
vis[v] = true;
for (auto &x : m_ad[v]) {
if (!vis[x]) {
topologicalSort(x, vis, stack);
}
}
stack.push_back(v);
}
void tDFS(int v, vector<bool> &vis, int compCount, vector<vector<int>> &comp) {
vis[v] = true;
comp[compCount - 1].push_back(v);
for (auto &x : m_tAd[v]) {
if (!vis[x]) {
tDFS(x, vis, compCount, comp);
}
}
}
void stronglyConnectedComponents() {
vector<bool> vis1(m_n + 1, false);
vector<bool> vis2(m_n + 1, false);
vector<int> stack;
int compCount = 0;
vector<vector<int>> comp;
for (int i = 1; i <= m_n; ++i) {
if (!vis1[i]) {
topologicalSort(i, vis1, stack);
}
}
for (int i = stack.size() - 1; i >= 0; --i) {
if (!vis2[stack[i]]) {
++compCount;
comp.emplace_back();
tDFS(stack[i], vis2, compCount, comp);
}
}
fout << compCount << '\n';
for (int i = 0; i < compCount; ++i) {
for (auto &x : comp[i]) {
fout << x << ' ';
}
fout << '\n';
}
}
// constructori
Graph(int n, vector<vector<int>> &ad) :
m_n(n), m_ad(ad), m_tAd() {}
Graph(int n, vector<vector<int>> &ad, vector<vector<int>> &tAd) :
m_n(n), m_ad(ad), m_tAd(tAd) {}
private:
int m_n;
vector<vector<int>> m_ad;
vector<vector<int>> m_tAd;
};
int main() {
int n, m, x, y;
fin >> n >> m;
vector<vector<int>> ad(n + 1);
vector<vector<int>> tAd(n + 1);
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
ad[x].push_back(y);
tAd[y].push_back(x);
}
Graph G(n, ad, tAd);
G.stronglyConnectedComponents();
return 0;
}