Pagini recente » Cod sursa (job #2966480) | Cod sursa (job #2229892) | Cod sursa (job #1868993) | Cod sursa (job #1652335) | Cod sursa (job #2083411)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,post[100001],nr,nrc;
bool viz[100001];
struct nod {
int val;
nod *next;
};
nod *v[100001],*vt[100001],*cc[100001];
void add_nod(nod *&cap,int val) {
nod *p=new nod;
p->val=val;
p->next=cap;
cap=p;
}
void citire_graf() {
f>>n>>m;
int x,y;
for(int i=1; i<=m; i++) {
f>>x>>y;
add_nod(v[x],y);
add_nod(vt[y],x);
}
}
void DFS(int i) {
viz[i]=1;
for(nod *p=v[i];p!=NULL;p=p->next)
if(!viz[p->val])
DFS(p->val);
post[++nr]=i;
}
void DFSt(int i) {
viz[i]=0;
add_nod(cc[nrc],i);
for(nod *p=vt[i];p!=NULL;p=p->next)
if(viz[p->val])
DFSt(p->val);
}
void comp_con() {
for(int i=1;i<=n;i++)
if(viz[i]==0)
DFS(i);
for(int i=n;i>0;i--)
if(viz[post[i]]==1) {
nrc++;
DFSt(post[i]);
}
}
void afisare() {
g<<nrc<<'\n';
for(int i=1;i<=nrc;i++) {
for(nod *p=cc[i];p!=NULL;p=p->next)
g<<p->val<<' ';
g<<'\n';
}
}
int main() {
citire_graf();
comp_con();
afisare();
return 0;
}