Cod sursa(job #3269143)

Utilizator aeru1Ianos Alex-Marian aeru1 Data 18 ianuarie 2025 11:37:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

#define TITLE "ctc"

ifstream f (TITLE".in");
ofstream g (TITLE".out");

int n,m;

bitset<100002> Visited;

int Topologic[100002],temp;

void TopDfs(int Node, vector<vector<int>> &Graph)
{
    Visited[Node]=true;
    for(auto it : Graph[Node])
        if(!Visited[it])
            TopDfs(it,Graph);
    Topologic[++temp]=Node;
}

void Dfs(int Node, vector<vector<int>> &Graph, vector<int> &Answer)
{
    Visited[Node]=true;
    Answer.push_back(Node);
    for(auto it : Graph[Node])
        if(!Visited[it])
            Dfs(it,Graph,Answer);
}

int main()
{
    f>>n>>m;
    vector<vector<int>> Graph(n+1),TGraph(n+1);
    while(m--)
    {
        int a,b;
        f>>a>>b;
        Graph[a].push_back(b);
        TGraph[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
        if(!Visited[i])
            TopDfs(i,Graph);
    Visited=0;
    vector<vector<int>>Answer;
    for(int i=n; i; i--)
        if(!Visited[Topologic[i]])
        {
            Answer.push_back(vector<int>());
            Dfs(Topologic[i],TGraph,Answer[Answer.size()-1]);
        }
    g<<Answer.size()<<'\n';
    for(auto it : Answer)
    {
        for(auto it2 : it)
            g<<it2<<' ';
        g<<'\n';
    }
    return 0;
}