Pagini recente » Rezultatele filtrării | Cod sursa (job #1272785) | Cod sursa (job #1272969) | soldiers | Cod sursa (job #3136233)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 5;
int n, m;
vector<int> G[NMAX];
int height[NMAX], highestJump[NMAX];
int noComp, compOfVertex[NMAX];
stack<int> s; // when in dfs(x), it contains those vertices in its subtree which aren't in a SCC yet
bool isOnStack[NMAX];
void dfs(int vertex) {
highestJump[vertex] = height[vertex];
s.push(vertex);
isOnStack[vertex] = true;
for (auto neighbor: G[vertex])
if (height[neighbor]) { // visited
if (isOnStack[neighbor]) // is a return edge (goes up)
highestJump[vertex] = min(highestJump[vertex], highestJump[neighbor]);
}
else { // tree edge
height[neighbor] = height[vertex] + 1;
dfs(neighbor);
highestJump[vertex] = min(highestJump[vertex], highestJump[neighbor]);
}
if (highestJump[vertex] == height[vertex]) {
// root of SCC
noComp++;
compOfVertex[vertex] = noComp;
while (s.top() != vertex) {
int x = s.top();
s.pop();
isOnStack[x] = false;
compOfVertex[x] = noComp;
}
s.pop();
isOnStack[vertex] = false;
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v; fin >> u >> v;
G[u].push_back(v);
}
for (int i = 1; i <= n; i++)
if (height[i] == 0) {
height[i] = 1;
dfs(i);
}
// for (int i = 1; i <= n; i++)
// cout << highestJump[i] << " ";
vector<vector<int>> verticesInComp(noComp + 1);
for (int i = 1; i <= n; i++)
verticesInComp[compOfVertex[i]].push_back(i);
fout << noComp << "\n";
for (int i = 1; i <= noComp; i++) {
for (int x : verticesInComp[i])
fout << x << " ";
fout << "\n";
}
return 0;
}