Pagini recente » Cod sursa (job #2242111) | Cod sursa (job #809512) | Cod sursa (job #658770) | Cod sursa (job #1555708) | Cod sursa (job #948516)
Cod sursa(job #948516)
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<vector>
using namespace std;
int a[100][100],k;
int index[100],leg[100],n,m,ind = 1;
vector <int> vec;
vector <int> vec2;
bool compar (int i,int j) { return (i>j); }
int min ( int a, int b) {
if ( a > b )
return b;
return a;
}
void tareconex (int v);
void tarjan () {
int i;
for ( i = 1; i <= n; i++)
if ( index[i] == 0 ){
tareconex(i);
}
}
void tareconex( int v ) {
index[v] = ind;
leg[v] = ind;
ind++;
vec.push_back(v);
int i,j;
for ( i = 1; i <= n; i++) {
if ( a[v][i] == 1 ) {
if ( index[i] == 0 ) {
tareconex(i);
leg[v] = min (leg[i], leg[v]);
}
else
for ( j = 0; j < vec.size(); j++)
if( i == vec[j])
leg[v] = min (leg[v], index[i]);
}
}
int x;
if ( leg[v] == index[v] ){
do {
x = vec.back();
vec.pop_back();
vec2.push_back(x);
}
while ( x != v) ;
sort(vec2.begin(), vec2.end(), compar);
while(!vec2.empty()) {
x = vec2.back();
vec2.pop_back();
printf("%d ",x);
}
printf("\n");
k++;
}
}
int main() {
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
int i,x,y;
scanf("%d%d", &n, &m);
for ( i = 1; i <= m; i++) {
scanf("%d%d", &x,&y);
a[x][y] = 1;
}
tarjan();
cout<<k;
return 0;
}