Pagini recente » Spargere | Istoria paginii utilizator/dtz.petrican | Taxe | Profil tabara | Cod sursa (job #2013640)
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100005;
int dep[N], low[N], st[N], depth, ls, ctc;
bool in_stack[N];
struct nod{
int nr;
nod *urm;
}*v[N];
struct lista{
int val;
lista *next;
}*l[N];
void adaug_nod(int x, int y){
nod *nou = new nod;
nou->nr = y;
nou->urm = v[x];
v[x] = nou;
}
void adaug_lista(int x, int y){
lista *p = new lista;
p->val = y;
p->next = l[x];
l[x] = p;
}
void push_stack(int val, int &ls){
st[++ls] = val;
in_stack[val] = true;
}
void new_ctc(int ns, int &ls){
ctc++;
do{
adaug_lista(ctc,st[ls]);
in_stack[st[ls]] = false;
}while(st[ls--] != ns);
}
void tarjan(int ns, int &l){
int nbr;
nod *q = v[ns];
low[ns] = dep[ns] = ++depth;
push_stack(ns,ls);
while(q){
nbr = q->nr;
if(dep[nbr] == 0){
tarjan(nbr,l);
low[ns] = min(low[ns], low[nbr]);
}
else if(in_stack[nbr])
low[ns] = min(low[ns], low[nbr]);
q = q->urm;
}
if(dep[ns] == low[ns])
new_ctc(ns,ls);
}
void print(int n){
lista *r = new lista;
out<<n<<"\n";
for(int i=1;i<=n;i++){
r = l[i];
while(r){
out<<r->val<<" ";
r = r->next;
}
out<<"\n";
}
}
int main()
{
int n,m,x,y;
in>>n>>m;
for(int i=1;i<=m;i++){
in>>x>>y;
adaug_nod(x,y);
}
in.close();
for(int i=1;i<=n;i++)
if(dep[i] == 0)
tarjan(i,ls);
print(ctc);
out.close();
return 0;
}