Pagini recente » Cod sursa (job #3188830) | Cod sursa (job #3285242) | Cod sursa (job #2400215) | Cod sursa (job #743316) | Cod sursa (job #3214284)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAXN 100000
#define MAXM 200000
using namespace std;
vector<vector<int>> v, vt; // vt = v transpus
stack<int> nodes;
bool visited[MAXN];
vector<vector<int>> r;
FILE *fin, *fout;
int n,m;
void dfs(int id){
visited[id] = true;
for(int i = 0; i < v[id].size(); i ++ )
if(!visited[v[id][i]])
dfs(v[id][i]);
nodes.push(id);
}
void double_dfs(int id, int start){
visited[id] = true;
r[start].push_back(id);
for(int i = 0; i < vt[id].size(); i ++ )
if(!visited[vt[id][i]])
double_dfs(vt[id][i], start);
}
void kosaraju(){
while(nodes.size())
nodes.pop();
for(int i = 0; i < n; i ++)
visited[i] = false;
for(int i = 0; i < n; i ++)
if(!visited[i])
dfs(i);
for(int i = 0; i < n; i ++)
visited[i] = false;
while(!nodes.empty()){
int node = nodes.top();
nodes.pop();
if(!visited[node])
double_dfs(node, node);
}
int nr = 0;
for(int i = 0; i < n; i ++){
if(r[i].size() > 0)
nr ++;
}
fprintf(fout, "%d\n", nr);
for(int i = 0; i < n; i ++){
if(r[i].size() > 0){
sort(r[i].begin(), r[i].end());
for(int j = 0; j < r[i].size(); j ++)
fprintf(fout, "%d ", r[i][j] + 1);
fprintf(fout, "\n");
}
}
}
void tarjan(){
// Not Implemented
}
int main(){
fin = fopen("ctc.in" ,"r");
fscanf(fin, "%d%d", &n, &m);
v.resize(n);
vt.resize(n);
r.resize(n);
for(int i = 0; i < m; i ++){
int a, b;
fscanf(fin, "%d%d", &a, &b);
v[a - 1].push_back(b - 1);
vt[b - 1].push_back(a - 1);
}
fclose(fin);
fout = fopen("ctc.out", "w");
kosaraju();
fclose(fout);
return 0;
}