Pagini recente » Cod sursa (job #1856387) | Cod sursa (job #611264) | Cod sursa (job #2735866) | Cod sursa (job #943579) | Cod sursa (job #1551233)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 10005;
vector <int> G[NMAX];
vector <int> S, dfs_discover, dfs_low, articulation_vertex, dfs_parent, visited,SCC[NMAX];
int t, dfsRoot, rootChildren, n, numSCC;
void articulationPoint(int u) {
int j, v;
++t;
dfs_discover[u] = dfs_low[u] = t;
for (j = 0; j < G[u].size(); ++j) {
v = G[u][j];
if (!dfs_discover[v]) {
dfs_parent[v] = u;
if (u == dfsRoot)
rootChildren++;
articulationPoint(v);
if (dfs_low[v] >= dfs_discover[u])
articulation_vertex[u] = true;
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
} else {
if (v != dfs_parent[u])
dfs_low[u] = min(dfs_low[u], dfs_discover[v]);
}
}
}
void tarjanSCC(int u) {
dfs_low[u] = dfs_discover[u] = ++t;
S.push_back(u); //stores u in a vector based on visitation order
visited[u] = 1;
for (int j = 0; j < (int) G[u].size(); j++) {
int v = G[u][j];
if (!dfs_discover[v])
tarjanSCC(v);
if (visited[v]) //condition for update
dfs_low[u] = min(dfs_low[u], dfs_low[v]);
}
if (dfs_low[u] == dfs_discover[u]) {
//if this is a root of an SCC
++numSCC;
while (1) {
int v = S.back();
S.pop_back();
visited[v] = 0;
SCC[numSCC].push_back(v);
if (u == v)
break;
}
}
}
int main() {
freopen("ap.in", "r", stdin);
freopen("ap.out", "w", stdout);
int m, u, v, i;
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
dfs_parent.assign(n + 1, -1);
articulation_vertex.assign(n + 1, 0);
dfs_low.assign(n + 1, 0);
dfs_discover.assign(n + 1, 0);
for (i = 1; i <= n; ++i)
if (!dfs_discover[i]) {
dfsRoot = i;
rootChildren = 0;
articulationPoint(i);
articulation_vertex[dfsRoot] = (rootChildren > 1);
}
dfs_discover.assign(n + 1, 0);
dfs_low.assign(n + 1, 0);
visited.assign(n + 1, 0);
t = numSCC = 0;
for (i = 1; i <= n; i++)
if (dfs_discover[i] == 0)
tarjanSCC(i);
printf("%d", numSCC);
printf("\n");
for(i=1;i<=numSCC;i++)
{
int nr=SCC[i].size();
for(int j=0;j<nr;j++)
printf("%d ", SCC[i][j]);
printf("\n");
}
return 0;
}