Pagini recente » Cod sursa (job #1578622) | Cod sursa (job #1413384) | Cod sursa (job #1704802) | Cod sursa (job #1889786) | Cod sursa (job #2927678)
#include <bits/stdc++.h>
#define MAX_N 20001
#define ll long long int
using namespace std;
unsigned n, m;
ifstream f("ctc.in");
ofstream gout("ctc.out");
struct Node {
vector < int > adj;
vector < int > rev_adj;
};
Node g[MAX_N];
stack < int > S;
stack < int > B;
int visited[MAX_N];
unsigned component[MAX_N];
vector < int > components[MAX_N];
int numComponents;
void dfs_1(int x) {
visited[x] = true;
for (unsigned i = 0; i < g[x].adj.size(); i++) {
if (!visited[g[x].adj[i]]) dfs_1(g[x].adj[i]);
}
S.push(x);
}
int t[MAX_N];
void dfs_2(int x) {
t[x]=numComponents;
component[x] = numComponents;
components[numComponents].push_back(x);
visited[x] = true;
for (unsigned i = 0; i < g[x].rev_adj.size(); i++) {
if (!visited[g[x].rev_adj[i]]) dfs_2(g[x].rev_adj[i]);
}
}
void Kosaraju() {
for (unsigned i = 1; i <=n; i++)
if (!visited[i]) dfs_1(i);
for (unsigned i = 1; i <=n; i++)
visited[i] = false;
while (!S.empty()) {
int v = S.top();
S.pop();
if (!visited[v]) {
dfs_2(v);
numComponents++;
}
}
}
int main() {
f >> n >> m;
int a, b;
while (m--) {
f >> a >> b;
g[a].adj.push_back(b);
g[b].rev_adj.push_back(a);
}
Kosaraju();
gout<<numComponents<<endl;
for(unsigned i=0;i<numComponents;i++)
{
for(unsigned j=1;j<=n;j++)
if(t[j]==i)
gout<<j<<" ";
gout<<endl;
}
return 0;
}