Pagini recente » Cod sursa (job #2949719) | Cod sursa (job #387884) | Cod sursa (job #1705258) | Cod sursa (job #37522) | Cod sursa (job #688562)
Cod sursa(job #688562)
#include<stdio.h>
#include<assert.h>
#include<vector>
#include<algorithm>
using namespace std;
const int kvert = 100005;
vector<int> graph[kvert];
vector<int> stack;
vector< vector<int> > str_con;
int n, m, vis[kvert], v_index[kvert], v_lowlink[kvert], instack[kvert];
void read(){
assert(freopen("ctc.in","r",stdin)!=NULL);
scanf("%d%d",&n ,&m);
int x, y;
for(int i = 1; i <= m; ++i){
scanf("%d%d",&x ,&y);
graph[x].push_back(y);
}
}
void dfs(int x){
vis[x] = 1;
v_lowlink[x] = v_index[x];
stack.push_back(x);
instack[x] = 1;
for(int i = 0; i < graph[x].size(); ++i){
if(!vis[graph[x][i]]){
v_index[graph[x][i]] = v_index[x] + 1;
dfs(graph[x][i]);
v_lowlink[x] = min(v_lowlink[x], v_lowlink[graph[x][i]]);
}
else if(instack[graph[x][i]])
v_lowlink[x] = min(v_lowlink[x], v_lowlink[graph[x][i]]);
}
if(v_lowlink[x] == v_index[x]){
vector<int> aux;
while(stack.back() != x){
aux.push_back(stack.back());
instack[stack.back()] = 0;
stack.pop_back();
}
aux.push_back(stack.back());
instack[x] = 0;
stack.pop_back();
str_con.push_back(aux);
aux.clear();
}
}
void solve(){
int i;
for(i = 1; i <= n; ++i)
if(!vis[i])
dfs(i);
}
void write(){
assert(freopen("ctc.out","w",stdout)!=NULL);
printf("%d\n",str_con.size());
int i, j;
for(i = 0; i < str_con.size(); ++i){
for(j = 0; j < str_con[i].size(); ++j)
printf("%d ",str_con[i][j]);
printf("\n");
}
}
int main(){
read();
solve();
write();
return 0;
}