Cod sursa(job #2827987)

Utilizator DMR6476Erdic Dragos DMR6476 Data 6 ianuarie 2022 18:14:02
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int theNeighbours[105][105];
int theIdexOfNeig[105];
bool isVisited[105];
int visitedStack[1005];
int theStack[1005];
int dr;
int transposedNeighbours[105][105];
int trasposedIndexOfNeighbour[105];
int theComponents[105][105];
int sizeOfComponent[105];
int scc;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void dfs2(int node)
{
    isVisited[node] = true;
    for(int i=0;i< trasposedIndexOfNeighbour[node];i++)
    {
        int currNode = transposedNeighbours[node][i];
        if(isVisited[currNode] == false)
            {
                theComponents[scc][sizeOfComponent[scc]] = currNode;
                ++sizeOfComponent[scc];
                dfs2(currNode);
            }
    }

}
void dfs(int node)
{
    isVisited[node] = true;
    for(int i=0; i<theIdexOfNeig[node]; i++)
    {
        int currNode = theNeighbours[node][i];
        if(isVisited[currNode] == false)
            dfs(currNode);
        }
    theStack[dr] = node;
    ++dr;
}
int main()
{
    //dfs
    //faci array-ul cu visited\
    //faci dfs pe transpus
    //cand elimini o componenta care nu e visited ai o noua componenta
    //tare conexa
    int n,m;
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int x,y;
        fin>>x>>y;
        theNeighbours[x][theIdexOfNeig[x]] = y;
        ++theIdexOfNeig[x];
        transposedNeighbours[y][trasposedIndexOfNeighbour[y]] = x;
        ++trasposedIndexOfNeighbour[y];

    }

    for(int i=1; i<=n; i++)
    {
        if(isVisited[i] == false)
            dfs(i);
    }
    for(int i=1; i<=n; i++)
        isVisited[i] = false;
    int st=0;

    --dr;
    while(0 <= dr)
    {
        if(isVisited[theStack[dr]] == false)
        {
            sizeOfComponent[scc] = 0;
            theComponents[scc][sizeOfComponent[scc]] = theStack[dr];
            ++sizeOfComponent[scc];
            dfs2(theStack[dr]);

            ++scc;
        }

        --dr;
    }
    fout<<scc<<"\n";
    for(int i=0;i<scc;i++)
    {

        sort(theComponents[i],theComponents[i]+sizeOfComponent[i]);
        for(int j=0;j<sizeOfComponent[i];j++)
            fout<<theComponents[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}