Pagini recente » Cod sursa (job #281331) | Cod sursa (job #157049) | Cod sursa (job #2016974) | Problema 2-satisfiabilității | Cod sursa (job #995364)
Cod sursa(job #995364)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N=100100;
vector<int> A[MAX_N];
int viz[MAX_N],hmin[MAX_N],h[MAX_N];
int st[MAX_N];
int num;
vector< vector<int> > sol;
void get_ctc(int nod) {
vector<int>ans;
int nact;
do {
nact=st[st[0]];
ans.push_back(nact);
st[0]--;
} while( st[0] && nact!=nod);
sol.push_back(ans);
}
void dfs(int nod) {
viz[nod]=1;
h[nod]=++num;
hmin[nod]=h[nod];
st[++st[0]]=nod;
for(vector<int>::iterator it=A[nod].begin(); it!=A[nod].end(); it++) {
if(!viz[*it]) {
dfs(*it);
hmin[nod]=min(hmin[nod],hmin[*it]);
}
else if(viz[*it]==1) {
hmin[nod]=min(hmin[nod],hmin[*it]);
}
}
if(hmin[nod]==h[nod]) {
get_ctc(nod);
}
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int x,y;
scanf("%d%d",&x,&y);
A[x].push_back(y);
}
for(int i=1;i<=n;i++) {
if(!viz[i]) {
dfs(i);
}
}
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++,printf("\n")) {
for(vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); it++) {
printf("%d ",*it);
}
}
return 0;
}