Pagini recente » Cod sursa (job #162537) | Cod sursa (job #1365638) | Cod sursa (job #2312980) | Cod sursa (job #3215419) | Cod sursa (job #2433963)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#include <string.h>
using namespace std;
struct FastInputReader {
int itr = 0;
string content;
FastInputReader(const string& file_name) {
ifstream fin(file_name);
content = string( (std::istreambuf_iterator<char>(fin) ),
(std::istreambuf_iterator<char>() ) );
}
FastInputReader& operator>>(int& v) {
v = 0;
while (!((content[itr]) >= '0' and (content[itr] <= '9'))) { itr += 1; }
while ((content[itr]) >= '0' and (content[itr] <= '9')) {
v *= 10;
v += content[itr] - '0';
itr += 1;
}
return *this;
}
} f("ctc.in");
ofstream g("ctc.out");
void tarjan(std::vector<std::vector<int>> &scc , const std::vector<int> *adj, const int src, int disc[],
int low[], std::vector<bool> &is_on_stack, std::stack<int> &s) {
static int time = 0;
disc[src] = low[src] = ++time;
s.push(src);
is_on_stack[src] = true;
for (auto it = adj[src].begin() ; it != adj[src].end(); ++it) {
if (disc[*it] == -1) {
tarjan(scc, adj, *it, disc, low, is_on_stack, s);
low[src] = std::min(low[src], low[*it]);
} else if (is_on_stack[*it] == true) {
low[src] = std::min(low[src], low[*it]);
}
}
if (disc[src] == low[src]) {
std::vector<int> comp;
int node;
do {
comp.push_back(node = s.top());
s.pop();
is_on_stack[node] = false;
} while(node != src);
scc.push_back(comp);
}
}
int main() {
//std::ifstream cin("ctc.in");
//std::ofstream cout("ctc.out");
//std::ios::sync_with_stdio(false);
int n, m, src, dest;
f >> n >> m;
std::vector<std::vector<int>> scc;
std::vector<int> adj[n];
int disc[n], low[n];
std::vector<bool> is_on_stack(n, false);
std::stack<int> s;
memset(disc, -1, sizeof(disc));
memset(low, 0, sizeof(disc));
for (; m ; --m) {
f >> src >> dest;
adj[src - 1].push_back(dest - 1);
}
for (int i = 0 ; i < n ; ++i) {
if (disc[i] == -1) {
tarjan(scc, adj, i, disc, low, is_on_stack, s);
}
}
g << scc.size() << '\n';
for (int i = 0 ; i < scc.size() ; ++i) {
for (int j = 0 ; j < scc[i].size() ; ++j) {
g << scc[i][j] + 1 << " ";
}
g << '\n';
}
return 0;
}