Pagini recente » Cod sursa (job #2573398) | Cod sursa (job #2002865) | Cod sursa (job #1528774) | Cod sursa (job #2862255) | Cod sursa (job #1131733)
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#define NR_MAX 100000
using namespace std;
vector<int>a[NR_MAX], ctc[NR_MAX];
int niv1[NR_MAX], niv2[NR_MAX], viz[NR_MAX], k=0, nr=0;
stack<int> st;
void dfs(int nod)
{
int j, u;
niv1[nod]=k;
niv2[nod]=k;
k++;
st.push(nod);
viz[nod]=1;
for(j=0; j<a[nod].size(); j++) {
u=a[nod][j];
if(niv1[u]==-1) {
dfs(u);
niv2[nod]=min(niv2[nod], niv2[u]);
}
else
if(viz[u]==1)
niv2[nod]=min(niv2[nod], niv1[u]);
}
if(niv1[nod]==niv2[nod]) {
do {
j=st.top();
viz[j]=0;
st.pop();
ctc[nr].push_back(j+1);
}while(j!=nod);
nr++;
}
}
int main()
{
FILE *fin, *fout;
fin=fopen("ctc.in", "r");
fout=fopen("ctc.out", "w");
int i, m, n, x, y, j;
fscanf(fin, "%d %d", &n, &m);
for(i=1; i<=m; i++) {
fscanf(fin, "%d %d", &x, &y);
a[x-1].push_back(y-1);
}
for(i=0; i<n; i++) {
niv1[i]=-1;
viz[i]=0;
}
for(i=0; i<n; i++)
if(niv1[i]==-1)
dfs(i);
fprintf(fout, "%d\n", nr);
for(i=0; i<nr; i++) {
for(j=0; j<ctc[i].size(); j++)
fprintf(fout, "%d ", ctc[i][j]);
fprintf(fout, "\n");
}
}