Pagini recente » Cod sursa (job #416934) | Cod sursa (job #411636) | Cod sursa (job #2179712) | Cod sursa (job #1289064) | Cod sursa (job #2101075)
#include <bits/stdc++.h>
#define MAXN 100000
std::vector <int> G[1 + MAXN];
std::vector <int> SCC;
std::vector <std::vector<int>> M;
int pos[1 + MAXN], lowlink[1 + MAXN];
int st[1 + MAXN], last, instack[1 + MAXN];
int indecs;
void tarjan(int node){
st[++last] = node;
instack[node] = 1;
pos[node] = lowlink[node] = ++indecs;
for(auto y:G[node]){
if(!pos[y])
tarjan(y), lowlink[node] = std::min(lowlink[node], lowlink[y]);
else if(instack[y])
lowlink[node] = std::min(lowlink[node], lowlink[y]);
}
if(pos[node] == lowlink[node]){
int x;
SCC.clear();
do{
x = st[last--];
SCC.push_back(x);
instack[x] = 0;
}while(x != node);
M.push_back(SCC);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("ctc.in","r");
fo = fopen("ctc.out","w");
int n, m;
fscanf(fi,"%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int x, y;
fscanf(fi,"%d%d", &x, &y);
G[x].push_back(y);
}
for(int i = 1; i <= n; i++)
if(!pos[i]) tarjan(i);
fprintf(fo,"%d\n", M.size());
for(int i = 0; i < M.size(); i++){
for(int j = 0; j < M[i].size(); j++)
fprintf(fo,"%d ", M[i][j]);
fprintf(fo,"\n");
}
fclose(fi);
fclose(fo);
return 0;
}