Cod sursa(job #1650861)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 11 martie 2016 21:05:59
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int N,M;
vector<int> lv[100005];
vector<int> lvreverse[100005];
vector<int> componente[100005];
priority_queue<pair<int,int> > q;
queue<int> qbfs;

int v1[100005],v2[100005],viz[100005];
int grad,nr;
void DFS(int n)
{
    viz[n]=1;
    grad++;
    for(vector<int>::iterator ii=lv[n].begin();ii!=lv[n].end();ii++)
    {
        int v = *ii;
        if(!viz[v])
            DFS(v);
    }
    q.push(make_pair(++grad,n));
}

void BFS(int n)
{

    viz[n]=1;
    qbfs.push(n);
    componente[nr].push_back(n);
    while(!qbfs.empty())
    {
        int u = qbfs.front();
        qbfs.pop();
        for(vector<int>::iterator ii=lvreverse[u].begin();ii!=lvreverse[u].end();ii++)
        {
            int v = *ii;
            if(!viz[v])
            {
                viz[v]=1;
                qbfs.push(v);
                componente[nr].push_back(v);
            }
        }
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int i;
    scanf("%d%d",&N,&M);

    for(i=1;i<=M;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        lv[x].push_back(y);
        lvreverse[y].push_back(x);
    }
    DFS(1);
    memset(viz,0,sizeof(viz));

    while(!q.empty())
    {
        int a = q.top().second;
        if(!viz[a])
            {
                nr++;
                BFS(a);
            }
        q.pop();

    }
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
    {
        for(vector<int>::iterator ii = componente[i].begin();ii!=componente[i].end();ii++)
        {
            printf("%d ",*ii);
        }
        printf("\n");
    }
    return 0;
}