Pagini recente » Cod sursa (job #494798) | Cod sursa (job #1233431) | Cod sursa (job #170691) | Cod sursa (job #1650593) | Cod sursa (job #1905631)
#include <fstream>
#include <vector>
#define NMAX 100010
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int disc[NMAX],low[NMAX],n,m;
bool instack[NMAX];
vector <int> st;
struct nod{
int vf;
nod* urm;
};
nod* v[NMAX];
int nrctc;
vector <int> ctc[NMAX];
ifstream f("ctc.in");
ofstream g("ctc.out");
void dfs(int u){
static int cnt=0;
disc[u]=low[u]=++cnt;
st.push_back(u);
instack[u]=true;
nod* q;
for(q=v[u];q;q=q->urm){
int w=(int)q->vf;
if(disc[w]==-1){
dfs(w);
low[u]=min(low[u],low[w]);
}else{
if(instack[w]==true)
low[u]=min(low[u],disc[w]);
}
}
int w=0;
if(low[u]==disc[u]){
++nrctc;
while(st.back()!=u)
{
w=(int) st.back();
ctc[nrctc].push_back(w);
instack[w]=false;
st.pop_back();
}
w=(int)st.back();
ctc[nrctc].push_back(w);
instack[w]=false;
st.pop_back();
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
f>>a>>b;
nod* q=new nod;
q->vf=b;
q->urm=v[a];
v[a]=q;
}
for(int i=1;i<=n;i++){
disc[i]=low[i]=-1;
instack[i]=false;
}
for(int i=1;i<=n;i++)
if(disc[i]==-1)
dfs(i);
g<<nrctc<<'\n';
for(int i=1;i<=nrctc;++i){
for(vector <int> ::iterator it=ctc[i].begin();it<ctc[i].end();++it)
g<<*it<<" ";
g<<'\n';
}
return 0;
}