Cod sursa(job #3168776)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 13 noiembrie 2023 11:53:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.21 kb
#include <bits/stdc++.h>
using namespace std;
///TOGGLES ---------------------------------------------
//#define INDEX_0
//#define int long long
//#define DEBUG
//#define LOCAL
//#define DEBUG_READ
#ifndef LOCAL
#define FIO
#endif // LOCAL
///DEFINES ---------------------------------------------


#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define iter(x) x::iterator
#define z(x) (x&(-x))
#define fr first
#define se second
#define mp make_pair
#ifdef INDEX_0
    #define forn(i,n) for(int i=0;i<n;i++)
#else
    #define forn(i,n) for(int i=1;i<=n;i++)
#endif // INDEX_0
#define forit(i,n) for(auto i:n)
#define IOS ios::sync_with_stdio(0);\
            cin.tie(0);\
            cout.tie(0);

#ifdef FIO
    const string name = "ctc";
    ifstream in(name+".in");
    ofstream out(name+".out");
    #define cin in
    #define cout out
#endif // FIO


typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<vector<int>> vvi;
typedef vector<vector<pii>> vvp;
typedef const int cint;
typedef long long ll;

///CONSTANTS ---------------------------------------------


cint MN = 1e5+5;
cint MQ = 5e5+5;
cint M = 1e9+5;
cint MB = 31;
cint MV = (1<<MB);

///GLOBALS ---------------------------------------------


int n, m;

vector<int> adj[MN];
int inStack[MN], order[MN], lowlink[MN];
int ordk=0;
bool vis[MN];
vector<int> stk;
vector<vector<int>> ctc;


///CODE ---------------------------------------------

void dfs(int nod)
{
    vis[nod]=1;
    inStack[nod]=1;
    lowlink[nod]=order[nod]=++ordk;
    stk.push_back(nod);
    //cout<<"entering "<<nod<<' '<<lowlink[nod]<<' '<<order[nod]<<'\n';
    for(auto e:adj[nod])
    {
        if(inStack[e])
        {
            lowlink[nod]= min(lowlink[nod], order[e]);
        }
        else if(!vis[e])
        {
            dfs(e);
            lowlink[nod]= min(lowlink[nod], lowlink[e]);
        }
    }
    //cout<<"leaving "<<nod<<' '<<lowlink[nod]<<' '<<order[nod]<<'\n';
    if(lowlink[nod]==order[nod])
    {
        //avem o componenta
        ctc.push_back(vector<int>());
        int nxt=0;
        do
        {
            nxt=stk.back();
            stk.pop_back();
            ctc.back().push_back(nxt);
            inStack[nxt]=0;
        }   while(nxt!=nod);
    }
}

#ifdef DEBUG_READ
    void debugRead()
    {

    }
#endif // DEBUG_READ

void readInput()
{
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        adj[a].push_back(b);
    }
}



void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }
    cout<<ctc.size()<<'\n';
    for(auto comp:ctc)
    {
        for(auto e:comp)
        {
            cout<<e<<' ';
        }
        cout<<'\n';
    }
}

int32_t main()
{
    IOS;

    int t = 1;
    //cin >> t;
    #ifdef LOCAL
        cout<<"running locally!\n"<<'\n';
    #endif // LOCAL
    while (t--)
    {
        #ifdef DEBUG_READ
            debugRead();
        #else
            readInput();
        #endif // DEBUG_READ
        solve();
    }
}


/*
8 12
1 2
2 6
6 7
7 6
3 1
3 4
2 3
4 5
5 4
6 5
5 8
8 7
*/