Pagini recente » Cod sursa (job #2254290) | Cod sursa (job #2438591) | Cod sursa (job #2211803) | Cod sursa (job #1043563) | Cod sursa (job #900275)
Cod sursa(job #900275)
#include<fstream>
#include<vector>
using namespace std;
#define max_n 100100
ifstream f("ctc.in");
ofstream g("ctc.out");
int ctc , n , nr , m , a , b , nod2 , j , x;
int index[max_n] , down[max_n] , stiva[max_n];
vector<int> L[max_n];
vector<int> V[max_n];
void read(){
f>> n >> m;
for(int i = 1 ; i <= m ; i++){
f>> a >> b;
L[a].push_back(b);
}
}
int minim(int a , int b){
if(a < b)
return a;
return b;
}
void dfs(int nod){
index[nod] = down[nod] = (++nr);
int nod2;
stiva[ ++stiva[ 0 ] ] = nod;
for(int i = 0 ; i < L[nod].size() ; i++){
nod2 = L[nod][i];
if( index[nod2] == 0 )
dfs(nod2);
if( index[nod2] > 0 )
down[nod] = minim( down[nod2] , down[nod] );
}
if( index[nod] == down[nod] ){
ctc++;
int x;
do{
x = stiva[ stiva[0]-- ];
index[x] = - index[x];
V[ctc].push_back( x );
}while( x != nod );
}
}
void solve(){
for(int i = 1 ; i <= n ; i++)
if(index[i] == 0)
dfs(i);
}
void print(){
g<< ctc << "\n";
for(int i = 1 ; i <= ctc ; i++){
for( j = 0 ; j < V[i].size() ; j++ )
g<< V[i][j] << " ";
g<< "\n";
}
}
int main(){
read();
solve();
print();
return 0;
}