Pagini recente » Cod sursa (job #2247116) | Cod sursa (job #136980) | Cod sursa (job #1604043) | Cod sursa (job #2470006) | Cod sursa (job #2561091)
#include <fstream>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int N=10003;
int ctc[N],viz[N],vizinv[N];
struct nod
{
int et;
nod* adr;
};
struct stiva
{
int et;
stiva *adr;
} *ct[N];
nod* l[N],*inv[N];
int c=0;
void dfs(int x, int k)
{
viz[x]=k;
for(nod* a=l[x];a!=NULL;a=a->adr)
{
if(viz[a->et]!=k)
{
viz[a->et]=k;
dfs(a->et,k);
}
}
}
void dfsinv(int y,int k)
{
vizinv[y]=k;
for(nod* b=inv[y];b!=NULL;b=b->adr)
{
if(vizinv[b->et]!=k)
{
vizinv[b->et]=k;
dfsinv(b->et,k);
}
}
if(viz[y]==k && vizinv[y]==k)
{
ctc[y] = k;
stiva *p = new stiva;
p -> et = y;
p -> adr = ct[k];
ct[k] = p;
}
}
int main() {
int n,m,x,y;
fin>>n>>m;
for(int i=1;i<=m;++i)
{
fin>>x>>y;
nod* p=new nod;
p->et=y;
p->adr=l[x];
l[x]=p;
p=new nod;
p->et=x;
p->adr=inv[y];
inv[y]=p;
}
int k = 0;
for(int i=1;i<=n;++i)
{
if(ctc[i]==0)
{
++k;
dfs(i, k);
dfsinv(i, k);
}
}
fout << k << '\n';
for (int i = 1; i <= k; ++i) {
for (stiva *a = ct[i]; a != NULL; a = a -> adr) {
fout << a->et << ' ';
}
fout << '\n';
}
}