Pagini recente » Borderou de evaluare (job #2875199) | Borderou de evaluare (job #2487421) | Borderou de evaluare (job #251443) | Borderou de evaluare (job #2174799) | Cod sursa (job #2412275)
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 100000
int n, m;
std::vector <int> G[1 + MAXN];
std::vector <int> invG[1 + MAXN];
std::vector <int> emptyVec;
std::vector <std::vector <int>> M;
int top[1 + MAXN], last;
bool seen[1 + MAXN];
void sortTop(int node){
seen[node] = 1;
for(auto y: G[node])
if(!seen[y]) sortTop(y);
top[++last] = node;
}
void dfs(int node){
seen[node] = 1;
M.back().push_back(node);
for(auto y: invG[node])
if(!seen[y]) dfs(y);
}
void Kosaraju(){
for(int i = 1; i <= n; i++)
if(!seen[i]) sortTop(i);
memset(seen, 0, sizeof(seen));
for(int i = n; i >= 1; i--)
if(!seen[top[i]]){
M.push_back(emptyVec);
dfs(top[i]);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("ctc.in","r");
fo = fopen("ctc.out","w");
fscanf(fi,"%d%d", &n, &m);
int i, x, y, j;
for(i = 0; i < m; i++){
fscanf(fi,"%d%d",&x, &y);
G[x].push_back(y);
invG[y].push_back(x);
}
Kosaraju();
fprintf(fo,"%d\n", M.size());
for(auto y: M){
for(auto z: y)
fprintf(fo,"%d ", z);
fprintf(fo,"\n");
}
return 0;
}