Pagini recente » Cod sursa (job #3293610) | Cod sursa (job #3294287) | Cod sursa (job #627952) | Clasament jc2020-runda2 | Cod sursa (job #3294283)
#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;
}