Cod sursa(job #2477833)

Utilizator ialexia_ioanaAlexia Ichim ialexia_ioana Data 21 octombrie 2019 10:36:54
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int NMAX=100005;
vector <int> g[2][NMAX];
bool viz[2][NMAX];
int ctc[NMAX];
int n, m, cc;
void RESET()
{
    for(int i=0; i<=n+3; i++)
        viz[0][i]=viz[1][i]=0;
}
void DFS(int u, int semn)
{
    int v;
    viz[semn][u]=1;
    for(int j=0; j<g[semn][u].size(); j++)
    {
        v=g[semn][u][j];
        if (!viz[semn][v])
            DFS(v, semn);
    }
}
int CTC()
{
    int cc=0;
    for(int i=1; i<=n; i++)
    {
        if (ctc[i]==0)
        {
            RESET();
            cc++;
            DFS(i, 0);
            DFS(i, 1);
            for(int j=1; j<=n; j++)
            {
                if (viz[0][j]==1 && viz[1][j]==1)
                    ctc[j]=cc/*, printf("%d ", j)*/;
            }
            //printf("\n");
        }
    }
    return cc;
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);
    int u, v, cc, i, j;
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d", &u, &v);
        g[0][u].push_back(v);
        g[1][v].push_back(u);
    }
    cc=CTC();
    printf("%d\n", cc);
    for(j=1; j<=cc; j++)
    {
        for(i=1; i<=n; i++)
        {
            if(ctc[i]==j)
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}