Cod sursa(job #2806125)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 13:18:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <stdio.h>
#include <deque>
#include <bitset>
#include <cstring>
#include <vector>

using namespace std;
FILE* f, * g;

int start1[100002], start2[100002];///dimensiunea=nr de noduri;
int t1[3][400002], t2[3][400002];///dimensiunea 2*nr de muchii
int succesor[100002], predecesor[100002], tot;
deque <int> q;
bitset <100002> viz1;
bitset <100002> viz2;
vector <int> vecini[100002];

void dfs1(int nod)
{
    int no;
    viz1[nod] = 1;
    no = start1[nod];
    while (no)
    {
        if (!viz1[t1[0][no]])
            dfs1(t1[0][no]);
        no = t1[1][no];

    }
    q.push_back(nod);
}
void dfs2(int nod)
{
    int no;
    viz2[nod] = 1;
    no = start2[nod];
    while (no)
    {
        if (!viz2[t2[0][no]])
            dfs2(t2[0][no]);
        no = t2[1][no];

    }
    vecini[tot].push_back(nod);
}

int main()
{
    int n, m, i, j, k1 = 0, o, cont, k2 = 0;
    f = fopen("ctc.in", "r");
    g = fopen("ctc.out", "w");
    fscanf(f, "%d %d", &n, &m);
    for (o = 1;o <= m;++o)
    {
        fscanf(f, "%d %d", &i, &j);
        ++k1;
        t1[0][k1] = j, t1[1][k1] = start1[i], start1[i] = k1;
        ++k2;
        t2[0][k2] = i, t2[1][k2] = start2[j], start2[j] = k2;
    }

    for (i = 1;i <= n;++i)
        if (!viz1[i])
            dfs1(i);
    /*while(!q.empty())
    {
        x=q.front();
        fprintf(g,"%d ",x);
        q.pop_front();
    }*/
    int x;
    while (!q.empty())
    {
        x = q.back();
        q.pop_back();
        if (!viz2[x])
            dfs2(x), ++tot;
    }
    fprintf(g, "%d\n", tot);
    for (i = 0;i < tot;++i)
    {
        for (j = 0;j < vecini[i].size();++j)
            fprintf(g, "%d ", vecini[i][j]);
        fprintf(g, "\n");
    }



    fclose(f);
    fclose(g);
    return 0;
}