Pagini recente » Cod sursa (job #125913) | Cod sursa (job #3289036) | Cod sursa (job #3219934) | Cod sursa (job #138311) | Cod sursa (job #238922)
Cod sursa(job #238922)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100001;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX];
stack<int> S;
int N,M,s[NMAX],nr[NMAX],low[NMAX];
bool u[NMAX];
vector< vector<int> > C;
int nc,index;
vector<int> aux;
void DF(int vf){
int k;
vector<int>::iterator it;
S.push(vf);
u[vf]=true;
nr[vf]=++index;
low[vf]=nr[vf];
for (it=G[vf].begin();it!=G[vf].end();++it)
if (!nr[*it])
DF(*it),low[vf]=min(low[vf],low[*it]);
else
if (u[*it]) low[vf]=min(low[vf],low[*it]);
if (low[vf]==nr[vf]){
++nc;
aux.clear();
do {
k=S.top();
S.pop();
u[k]=false;
aux.push_back(k);
}
while (k!=vf);
C.push_back(aux);
}
}
int main(){
int i,j;
vector<int>::iterator it;
fin>>N>>M;
while (M--){
fin>>i>>j;
G[i].push_back(j);
}
for (i=1;i<=N;++i)
if (!nr[i]) DF(i);
fout<<nc<<'\n';
for (i=0;i<nc;++i){
for (it=C[i].begin();it!=C[i].end();++it)
fout<<*it<<' ';
fout<<'\n';}
return 0;
}