Pagini recente » Cod sursa (job #594702) | Cod sursa (job #211822) | Cod sursa (job #1758203) | Cod sursa (job #3142012) | Cod sursa (job #2927674)
#include <bits/stdc++.h>
#define MAX_N 20001
#define ll long long int
using namespace std;
int 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];
int component[MAX_N];
vector < int > components[MAX_N];
int numComponents;
void dfs_1(int x) {
visited[x] = true;
for (int 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 (int 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 (int i = 1; i <=n; i++)
if (!visited[i]) dfs_1(i);
for (int 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() {
cin >> n >> m;
int a, b;
while (m--) {
cin >> a >> b;
g[a].adj.push_back(b);
g[b].rev_adj.push_back(a);
}
Kosaraju();
cout<<numComponents<<endl;
for(int i=0;i<numComponents;i++)
{
for(int j=1;j<=n;j++)
if(component[j]==i)
cout<<j<<" ";
cout<<endl;
}
return 0;
}