Cod sursa(job #1232231)

Utilizator gapdanPopescu George gapdan Data 22 septembrie 2014 15:30:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 100001
using namespace std;
int n,nr,m,i,x,y,k;
vector<int>v1[NMAX],v2[NMAX];
int viz1[NMAX],viz2[NMAX],sol[NMAX];
struct solutie
{
    int nrcmp,ind;
}a[NMAX];
void DFS(int nod)
{
    viz1[nod]=1;
    vector<int>::iterator it;
    for (it=v1[nod].begin();it!=v1[nod].end();++it)
    {
        if (viz1[*it]==0) DFS(*it);
    }
    sol[++k]=nod;
}
void DF(int nod)
{
    viz2[nod]=1;
    a[nod].ind=nod;
    a[nod].nrcmp=nr;
    vector<int>::iterator it;
    for (it=v2[nod].begin();it!=v2[nod].end();++it)
    {
        if (viz2[*it]==0) DF(*it);
    }
}
int cmp(solutie r,solutie p)
{
    if (r.nrcmp>p.nrcmp) return 0;
        else if (r.nrcmp==p.nrcmp && r.ind>p.ind) return 0;
        else return 1;
}
void sortaret()
{
    for (int i=1;i<=n;++i)
    {
        if (viz1[i]==0) DFS(i);
    }
}
void ctc()
{
    nr=0;
    for (int i=k;i>=1;--i)
    {
        if (viz2[sol[i]]==0) DF(sol[i]),++nr;
    }
    sort(a+1,a+n+1,cmp);
}
void afis()
{
    printf("%d\n",nr);
    a[0].nrcmp=a[1].nrcmp;
    for (i=1;i<=n;++i)
        {
            if (a[i].nrcmp!=a[i-1].nrcmp) printf("\n%d ",a[i].ind);
                else printf("%d ",a[i].ind);
        }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    sortaret();
    ctc();
    afis();
    return 0;
}