Cod sursa(job #2176370)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 17 martie 2018 00:01:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<vector>
 
using namespace std;
 
int n,m;
int vec[100010],pos_in_vec[100010],pos;
int index[100010],lowlink[100010],max_index;
vector<int> adj[100010];
vector<int> ctc[100010];
int ctc_count;
 
int tarjan(int nod)
{
    //printf("^ %d\n",nod);
    max_index++;
    index[nod]=max_index;
    lowlink[nod]=max_index;
    pos++;
    pos_in_vec[nod]=pos;
    vec[pos]=nod;
 
    for(vector<int>::iterator it=adj[nod].begin();it!=adj[nod].end();it++)
    {
        if(index[*it]==0)
        {
            tarjan(*it);
            lowlink[nod]=min(lowlink[nod],lowlink[*it]);
        }
        else if(pos_in_vec[*it]!=0)
        {
            lowlink[nod]=min(lowlink[nod],index[*it]);
        }
    }
 
    //printf("*** %d %d %d\n",nod,lowlink[nod],index[nod]);
    if(lowlink[nod]==index[nod])
    {
        int temp=pos;
        pos=pos_in_vec[nod]-1;
        ctc_count++;
        for(int i=pos+1;i<=temp;i++)
        {
            ctc[ctc_count].push_back(vec[i]);
            pos_in_vec[vec[i]]=0;
            //printf(" $ %d %d\n",vec[i],i);
        }
    }
}
 
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
 
    scanf("%d %d",&n,&m);
 
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        adj[x].push_back(y);
    }
 
    for(int i=1;i<=n;i++)
    {
        if(index[i]==0)
        {
            tarjan(i);
        }
    }
 
    printf("%d\n",ctc_count);
    for(int i=1;i<=ctc_count;i++)
    {
        for(vector<int>::iterator it=ctc[i].begin();it!=ctc[i].end();it++)
        {
            printf("%d ",*it);
        }
        printf("\n");
    }
}