Cod sursa(job #3243172)

Utilizator Laurentiu_BTarabic Laurentiu Gabriel Laurentiu_B Data 16 septembrie 2024 10:34:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<bits/stdc++.h>
using namespace std;

int n,m,w[100001],nr=0;

vector<int> a[100001];
vector<int> b[100001];
vector<int> ans[100001];

vector<int> order;

void dfs(int v, vector<int> adj[100001], vector<int> &ordering)
{
    w[v] = 1;

    for(int i=0;i<adj[v].size();i++)
        if(!w[adj[v][i]])
            dfs(adj[v][i], adj, ordering);
    ordering.push_back(v);
}

void unite()
{
    for(int i=1;i<=n;i++)
        if(!w[i])
            dfs(i, a, order);

    for(int i=1;i<=n;i++)
        w[i]=0;

    for(int i=order.size()-1;i>=0;i--)
    {
        int x=order[i];

        vector<int> comp;

        if(!w[x]){

        dfs(x, b, comp);

        nr++;

        for(int i=0;i<comp.size();i++)
        {
            ans[nr].push_back(comp[i]);
        }
        }
    }
}

int main()
{

    ifstream cin("ctc.in");
    ofstream cout("ctc.out");

    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }

    unite();

    cout<<nr<<endl;

    for(int i=1;i<=nr;i++)
    {
        for(int j=0;j<ans[i].size();j++)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }
}