Pagini recente » Cod sursa (job #1938829) | Cod sursa (job #734442) | Cod sursa (job #68897) | Cod sursa (job #2672809) | Cod sursa (job #3195868)
#include <bits/stdc++.h>
#define pb push_back
typedef std::vector<int> vi;
typedef std::vector<vi> vii;
class InParser {
private:
std::vector<char> str;
int ptr;
std::ifstream fin;
private:
char get_char() {
if (ptr == (int)str.size()) {
fin.read(str.data(), (int)str.size());
ptr = 0;
}
return str[ptr++];
}
template<class T>
T get_int() {
char chr;
do {
chr = get_char();
} while (!isdigit(chr) && (chr != '-'));
int sgn = +1;
if (chr == '-') {
sgn = -1;
chr = get_char();
}
T num = 0;
while (isdigit(chr)) {
num = num * 10 + (chr - '0');
chr = get_char();
}
return sgn * num;
}
public:
InParser(const char *name) : str((int)1e5), ptr((int)1e5), fin(name) { }
~InParser() { fin.close(); }
template<class T>
friend InParser &operator >> (InParser &in, T &num) {
num = in.get_int<T>();
return in;
}
};
class OutParser {
private:
std::vector<char> str;
int ptr;
std::ofstream fout;
private:
void put_char(char chr) {
if (ptr == (int)str.size()) {
fout.write(str.data(), (int)str.size());
ptr = 0;
}
str[ptr++] = chr;
}
template<class T>
void put_int(T num) {
if (num < 0) {
put_char('-');
num *= -1;
}
if (num > 9)
put_int(num / 10);
put_char(num % 10 + '0');
}
public:
OutParser(const char *name) : str((int)1e5), ptr(0), fout(name) { }
~OutParser() {
fout.write(str.data(), ptr);
fout.close();
}
template<class T>
friend OutParser &operator << (OutParser &out, const T num) {
out.put_int(num);
return out;
}
friend OutParser &operator << (OutParser &out, const char chr) {
out.put_char(chr);
return out;
}
friend OutParser &operator << (OutParser &out, const char *s) {
for (int i = 0; s[i]; i++)
out.put_char(s[i]);
return out;
}
};
InParser fin("ctc.in");
OutParser fout("ctc.out");
int n, m;
std::vector<bool> vis;
std::stack<int> st;
vii adj, adj_t;
vi comp;
void load() {
fin >> n >> m;
adj.resize(n + 1);
adj_t.resize(n + 1);
vis.resize(n + 1);
while (m--) {
int u, v;
fin >> u >> v;
adj[u].pb(v);
adj_t[v].pb(u);
}
}
void dfs(int node, int pass) {
vis[node] = true;
vi &adj_list = (pass == 1) ? adj[node] : adj_t[node];
for (auto neighbor : adj_list)
if (!vis[neighbor])
dfs(neighbor, pass);
if (pass == 1)
st.push(node);
else
comp.pb(node);
}
void kosaraju() {
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs(i, 1);
fill(vis.begin(), vis.end(), false);
vii sol;
while (!st.empty()) {
int node = st.top();
st.pop();
if (!vis[node]) {
dfs(node, 2);
sol.pb(comp);
comp.clear();
}
}
fout << (int)sol.size() << '\n';
for (auto scc : sol) {
for (auto node : scc)
fout << node << ' ';
fout << '\n';
}
}
int main() {
load();
kosaraju();
return 0;
}