Pagini recente » Cod sursa (job #675252) | Cod sursa (job #2917305) | Cod sursa (job #465709) | Cod sursa (job #1788356) | Cod sursa (job #1340371)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#define DIM 100011
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,ctc,k;
int low[DIM],niv[DIM];
vector<int> L[DIM],sol[DIM];
stack<int> S;
bitset<DIM> viz,IS;
void dfs(int nod){
vector<int>::iterator it;
int x;
k++;
low[nod]=niv[nod]=k;
S.push(nod);
viz[nod]=IS[nod]=1;
for(it=L[nod].begin();it!=L[nod].end();it++){
if(!viz[*it]){
dfs(*it);
low[nod]=min(low[nod],low[*it]);
}
else if(IS[nod])
low[nod]=min(low[nod],low[*it]);
}
if(low[nod]==niv[nod]){
//componenta conexa
ctc++;
do{x=S.top(),S.pop();
IS[x]=0;
sol[ctc].push_back(x);
}while(x!=nod);
}
}
int main(void){
register int x,y,i,j;
vector<int>::iterator it;
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
L[x].push_back(y);
}
for(i=1;i<=n;i++){
if(!viz[i])
dfs(i);
}
g<<ctc<<"\n";
for(i=1;i<=ctc;i++){
for(it=sol[i].begin();it!=sol[i].end();it++)
g<<*it<<" ";
g<<"\n";
}
f.close();
g.close();
return 0;
}