Cod sursa(job #1498219)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 8 octombrie 2015 09:56:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <bitset>
#define nmax 100005
using namespace std;
int n,m,a;
vector <int> v[nmax],p[nmax];
vector <int> l[nmax];
stack <int> s;
bitset <nmax> b;



void dfsgraph(int x)
{
    b[x]=1;
    for (int i=0;i<v[x].size();i++)
        if (!b[v[x][i]])
            dfsgraph(v[x][i]);
    s.push(x);
}
void dfstrans(int x)
{
    b[x]=1;
    l[a].push_back(x);
    for (int i=0;i<p[x].size();i++)
        if (!b[p[x][i]])
            dfstrans(p[x][i]);

}

void kosaraju()
{
    int i,j,x;
    for (i=1;i<=n;i++)
        if (!b[i])
            dfsgraph(i);
    b.reset();
    while (!s.empty()) {
        x=s.top();
        s.pop();
        if (b[x]==0)
            a++,dfstrans(x);
    }
    printf("%d\n",a);

    for (i=1;i<=a;i++) {
        sort(l[i].begin(),l[i].end());
        for (j=0;j<l[i].size();j++)
                printf("%d ",l[i][j]);
        printf("\n");
    }

}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        p[y].push_back(x);
    }
    kosaraju();

    return 0;
}