Pagini recente » Cod sursa (job #2145827) | Cod sursa (job #2412842) | Cod sursa (job #1184294) | Cod sursa (job #2226916) | Cod sursa (job #3228866)
#include <bits/stdc++.h>
using namespace std;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
// numarul maxim de noduri
static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
vector<int> adj[NMAX];
vector<int>parent;
vector<int>low_link;
vector<int>found;
vector<bool>in_stack;
stack<int>nodes_stack;
void read_input() {
ifstream fin("ctc.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y); // arc (x, y)
}
fin.close();
}
vector<vector<int>> tarjan(){
vector<vector<int>> all_sccs;
parent=vector<int>(n+1,-1);
low_link=vector<int>(n+1,-1);
found=vector<int>(n+1,-1);
in_stack=vector<bool>(n+1,false);
int timestamp=0;
for(int i=1;i<=n;++i)
if(parent[i]==-1) {
parent[i]=i;
dfs(i,timestamp,all_sccs);
}
return all_sccs;
}
void dfs(int node,int ×tamp,vector<vector<int>> &all_sccs){
found[node]=++timestamp;
low_link[node]=found[node];
nodes_stack.push(node);
in_stack[node]=true;
for(auto &neight:adj[node]){
if(parent[neight]!=-1){
if(in_stack[neight]){
low_link[node]=min(low_link[node],found[neight]);
}
continue;
}
parent[neight]=node;
dfs(neight,timestamp,all_sccs);
low_link[node]=min(low_link[node],low_link[neight]);
}
if(found[node]==low_link[node]){
vector<int>new_scc;
do{
auto x = nodes_stack.top();
nodes_stack.pop();
in_stack[x]=false;
new_scc.push_back(x);
} while(node!=new_scc.back());
all_sccs.push_back(new_scc);
}
}
vector<vector<int>> get_result() {
//
// TODO: Găsiți componentele tare conexe (CTC / SCC) ale grafului orientat cu n noduri, stocat în adj.
//
// Rezultatul se va returna sub forma unui vector, fiecare element fiind un SCC (adică tot un vector).
// * nodurile dintr-un SCC pot fi găsite în orice ordine
// * SCC-urile din graf pot fi găsite în orice ordine
//
// Indicație: Folosiți algoritmul lui Tarjan pentru SCC.
//
// vector<vector<int>> all_sccs;
// tarjan(all_sccs);
return tarjan();
}
void print_output(const vector<vector<int>>& all_sccs) {
ofstream fout("ctc.out");
fout << all_sccs.size() << '\n';
for (const auto& scc : all_sccs) {
for (auto node : scc) {
fout << node << ' ';
}
fout << '\n';
}
fout.close();
}
};
// [ATENTIE] NU modifica functia main!
int main() {
// * se aloca un obiect Task pe heap
// (se presupune ca e prea mare pentru a fi alocat pe stiva)
// * se apeleaza metoda solve()
// (citire, rezolvare, printare)
// * se distruge obiectul si se elibereaza memoria
auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
if (!task) {
cerr << "new failed: WTF are you doing? Throw your PC!\n";
return -1;
}
task->solve();
delete task;
return 0;
}