Cod sursa(job #3294283)

Utilizator EnnBruhEne Andrei EnnBruh Data 20 aprilie 2025 23:22:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.22 kb
#include <bits/stdc++.h>
using namespace std;


inline bool isdigit(char ch) {
        return '0' <= ch && ch <= '9';
}

#define buffsze 8192
class inParser {
private:
        FILE *fin; char *buff; unsigned short id;
        inline char readCh( ) {
                ++id;
                if (id == buffsze) { id = 0; fread(buff, sizeof(char), buffsze, fin); }
                return buff[id];
        }
public:
        inParser (const char *name) {
                fin = fopen(name, "r");
                buff = new char[buffsze]( );
                id = buffsze - 1;
        }

        inParser& operator >> (int& num) {
                char ch;
                while (!isdigit(ch = readCh( )));
                num = ch - '0';
                while (isdigit(ch = readCh( )))
                        num = num * 10 + ch - '0';
                return *this;
        }
};

class outParser {
private:
        FILE *fout; char *buff; unsigned short id;
        inline void writeCh(char ch) {
                ++id;
                if (id == buffsze) { id = 0; fwrite(buff, sizeof(char), buffsze, fout); }
                buff[id] = ch;
        }
public:
        outParser (const char *name) {
                fout = fopen(name, "w");
                buff = new char[buffsze]( );
                id = -1;
        }

        ~outParser ( ) {
                fwrite(buff, sizeof(char), id, fout);
        }

        outParser& operator << (int num) {
                if (num < 10) writeCh(num + '0');
                else {
                        (*this) << (num / 10);
                        writeCh(num % 10 + '0');
                }
                return *this;
        }

        outParser& operator << (char ch) {
                writeCh( ch );
                return *this;
        }
};

const string filename = "ctc";
inParser in ((filename + ".in").c_str( ));
outParser out ((filename + ".out").c_str( ));

const int maxsze = 1e5 + 2;
const int inf = 0x3f3f3f3f;
const int modulo = 1e9 + 7;


vector <int> adj[maxsze], rdj[maxsze];
bool visited[maxsze];
int after[maxsze], len, ans;
vector <int> scc[maxsze];
void dfs(int node) {
        visited[node] = true;
        for (auto neibor : adj[node]) {
                if (visited[neibor]) continue ;
                dfs( neibor );
        }

        after[++len] = node;
}

void rfs(int node) {
        visited[node] = false;

        scc[ans].push_back( node );
        for (auto neibor : rdj[node]) {
                if (!visited[neibor]) continue ;
                rfs( neibor );
        }
}

signed main( ) {
        int n, m; in >> n >> m;
        for (int i = 0; i < m; ++i) {
                int a, b; in >> a >> b;
                adj[a].push_back( b );
                rdj[b].push_back( a );
        }

        for (int i = 1; i <= n; ++i)
                if (!visited[i]) dfs( i );
        for (int i = len; i >= 1; --i)
                if (visited[after[i]]) {
                        ++ans;
                        rfs(after[i]);
                }

        out << ans << '\n';
        for (int i = 1; i <= ans; ++i, out << '\n')
                for (auto node : scc[i]) out << node << ' ';
        return 0;
}