Cod sursa(job #961495)

Utilizator geniucosOncescu Costin geniucos Data 12 iunie 2013 13:58:22
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int nr,poz,n,m,i,x1,y11,ap[100009],Q[100009];
queue < int > cc;
vector < int > a,v[100009],h[100009];
vector < vector < int > > ras;
vector < int > ::iterator it;
void dfs(int nod)
{
    vector < int > ::iterator it;
    ap[nod]=1;
    for(it=v[nod].begin();it!=v[nod].end();it++)
        if(ap[*it]==0) dfs(*it);
    nr++;
    Q[nr]=nod;
}
void afis()
{
    vector < int > a;
    printf("%d\n",ras.size());
    for(i=0;i<ras.size();i++)
    {
        a=ras[i];
        sort(a.begin(),a.end());
        printf("%d ",a.size());
        for(it=a.begin();it!=a.end();it++)
            printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
    scanf("%d",&x1);
    scanf("%d",&y11);
    v[x1].push_back(y11);
    h[y11].push_back(x1);
}
for(i=1;i<=n;i++)
    if(ap[i]==0) dfs(i);
for(i=1;i<=n;i++)
    ap[i]=0;
poz=nr;
while(1)
{
    while(ap[Q[poz]]==1) poz--;
    if(poz==0) break;
    cc.push(Q[poz]);
    a.clear();
    ap[Q[poz]]=1;
    a.push_back(Q[poz]);
    while(!cc.empty())
    {
        x1=cc.front();
        cc.pop();
        for(it=h[x1].begin();it!=h[x1].end();it++)
            if(ap[*it]==0)
            {
                ap[*it]=1;
                a.push_back(*it);
                cc.push(*it);
            }
    }
    ras.push_back(a);
}
afis();
return 0;
}