//-------------------------------------------------------------
// // sate
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <queue>
// using namespace std;
// const int MAXN = 30005;
// // Graful va reține perechi de tipul {vecin, cost_muchie}
// vector<pair<int, int>> adj[MAXN];
// bool vizitat[MAXN];
// int dist[MAXN];
// int main() {
// ifstream fin("sate.in");
// ofstream fout("sate.out");
// int N, M, X, Y;
// fin >> N >> M >> X >> Y;
// for (int k = 0; k < M; ++k) {
// int u, v, d;
// fin >> u >> v >> d;
// // Adăugăm muchia directă (cost pozitiv)
// adj[u].push_back({v, d});
// // Adăugăm muchia inversă (cost negativ)
// adj[v].push_back({u, -d});
// }
// // Parcurgere BFS plecând din X
// queue<int> q;
// q.push(X);
// vizitat[X] = true;
// dist[X] = 0;
// while (!q.empty()) {
// int u = q.front();
// q.pop();
// // Dacă am ajuns la satul căutat, ne putem opri
// if (u == Y) {
// break;
// }
// for (auto muchie : adj[u]) {
// int v = muchie.first;
// int cost = muchie.second;
// if (!vizitat[v]) {
// vizitat[v] = true;
// dist[v] = dist[u] + cost;
// q.push(v);
// }
// }
// }
// fout << dist[Y] << "\n";
// return 0;
// }
//-------------------------------------------------------------
// // alice 2
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <string>
// #include <queue>
// using namespace std;
// int main() {
// ifstream fin("alice2.in");
// ofstream fout("alice2.out");
// string s;
// fin >> s;
// int n = s.length();
// // Caz de bază: cuvânt de o literă
// if (n <= 1) {
// fout << 0 << "\n";
// return 0;
// }
// vector<int> prev_pos(n, -1);
// vector<int> next_pos(n, -1);
// // Precalculare salturi la stânga
// vector<int> last_seen(26, -1);
// for (int i = 0; i < n; ++i) {
// int char_idx = s[i] - 'a';
// if (last_seen[char_idx] != -1) {
// prev_pos[i] = last_seen[char_idx];
// }
// last_seen[char_idx] = i;
// }
// // Precalculare salturi la dreapta
// vector<int> first_seen(26, -1);
// for (int i = n - 1; i >= 0; --i) {
// int char_idx = s[i] - 'a';
// if (first_seen[char_idx] != -1) {
// next_pos[i] = first_seen[char_idx];
// }
// first_seen[char_idx] = i;
// }
// // BFS pentru drum minim
// vector<int> dist(n, -1);
// queue<int> q;
// q.push(0);
// dist[0] = 0;
// while (!q.empty()) {
// int u = q.front();
// q.pop();
// // Dacă am ajuns la destinație, ne putem opri direct
// if (u == n - 1) {
// fout << dist[u] << "\n";
// return 0;
// }
// // Construim lista de vecini posibili
// vector<int> vecini;
// if (u > 0) vecini.push_back(u - 1);
// if (u < n - 1) vecini.push_back(u + 1);
// if (prev_pos[u] != -1) vecini.push_back(prev_pos[u]);
// if (next_pos[u] != -1) vecini.push_back(next_pos[u]);
// // Vizităm vecinii neexplorați
// for (int v : vecini) {
// if (dist[v] == -1) {
// dist[v] = dist[u] + 1;
// q.push(v);
// }
// }
// }
// return 0;
// }
// //-------------------------------------------------------------
// // EasyGraph
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <algorithm>
// using namespace std;
// const int MAXN = 15005;
// long long v[MAXN];
// vector<int> adj[MAXN];
// long long dp[MAXN];
// bool vizitat[MAXN];
// long long ans_max;
// // Funcția DFS care calculează DP-ul
// void dfs(int u) {
// vizitat[u] = true;
// long long max_fiu = 0; // Inițializăm cu 0 pentru cazul în care ne oprim în u
// for (int w : adj[u]) {
// if (!vizitat[w]) {
// dfs(w);
// }
// // După ce vecinul a fost calculat (sau era deja calculat), vedem dacă e profitabil
// max_fiu = max(max_fiu, dp[w]);
// }
// // Suma maximă plecând din u este valoarea lui u + cel mai bun drum prin fii
// dp[u] = v[u] + max_fiu;
// // Actualizăm răspunsul global
// ans_max = max(ans_max, dp[u]);
// }
// void rezolva_test(ifstream& fin, ofstream& fout) {
// int N, M;
// fin >> N >> M;
// for (int i = 1; i <= N; ++i) {
// fin >> v[i];
// adj[i].clear(); // Resetăm graful pentru noul test
// vizitat[i] = false; // Resetăm starea de vizitare
// }
// for (int i = 0; i < M; ++i) {
// int x, y;
// fin >> x >> y;
// adj[x].push_back(y);
// }
// ans_max = -2e18; // Inițializăm cu o valoare extrem de mică (nu 0!)
// // Graful poate fi format din mai multe componente conexe,
// // deci pornim DFS-ul din toate nodurile nevizitate.
// for (int i = 1; i <= N; ++i) {
// if (!vizitat[i]) {
// dfs(i);
// }
// }
// fout << ans_max << "\n";
// }
// int main() {
// ifstream fin("easygraph.in");
// ofstream fout("easygraph.out");
// int T;
// if (fin >> T) {
// while (T--) {
// rezolva_test(fin, fout);
// }
// }
// return 0;
// }
// //-------------------------------------------------------------
// // Path
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <string>
// #include <algorithm>
// using namespace std;
// const long long INF = 2000000005LL; // Un pic mai mare decât K-ul maxim permis
// // Funcții de conversie pentru a respecta ordinea: mici apoi mari
// int char_to_idx(char c) {
// if (c >= 'a' && c <= 'z') return c - 'a';
// return c - 'A' + 26;
// }
// char idx_to_char(int idx) {
// if (idx < 26) return 'a' + idx;
// return 'A' + idx - 26;
// }
// vector<int> adj[52];
// bool prezent[52];
// long long max_len[52];
// long long cnt[52];
// bool vizitat[52];
// void dfs(int u) {
// if (vizitat[u]) return;
// vizitat[u] = true;
// max_len[u] = 0;
// cnt[u] = 1; // Un drum de lungime 0 (nodul în sine)
// long long mx = 0;
// // Găsim lungimea maximă
// for (int v : adj[u]) {
// dfs(v);
// mx = max(mx, 1 + max_len[v]);
// }
// // Calculăm numărul de drumuri care au această lungime maximă
// if (mx > 0) {
// max_len[u] = mx;
// long long c = 0;
// for (int v : adj[u]) {
// if (1 + max_len[v] == mx) {
// c += cnt[v];
// if (c > INF) c = INF; // Plafonare pentru a evita overflow
// }
// }
// cnt[u] = c;
// }
// }
// int main() {
// ifstream fin("path.in");
// ofstream fout("path.out");
// int N, M;
// long long K;
// fin >> N >> M >> K;
// for (int i = 0; i < M; ++i) {
// char c1, c2;
// fin >> c1 >> c2;
// int u = char_to_idx(c1);
// int v = char_to_idx(c2);
// adj[u].push_back(v);
// prezent[u] = prezent[v] = true;
// }
// // Sortăm vecinii pentru a-i parcurge mereu în ordine lexicografică
// for (int i = 0; i < 52; ++i) {
// if (!adj[i].empty()) {
// sort(adj[i].begin(), adj[i].end());
// }
// }
// // Pas 1: Calculăm DP-urile pentru toate nodurile
// long long L_max = 0;
// for (int i = 0; i < 52; ++i) {
// if (prezent[i]) {
// dfs(i);
// L_max = max(L_max, max_len[i]);
// }
// }
// // Pas 2: Colectăm nodurile de start valide (care pot forma L_max)
// vector<int> starts;
// for (int i = 0; i < 52; ++i) {
// if (prezent[i] && max_len[i] == L_max) {
// starts.push_back(i);
// }
// }
// // Pas 3: Găsim nodul de start pentru al K-lea drum
// int curr = -1;
// for (int u : starts) {
// if (K <= cnt[u]) {
// curr = u;
// break;
// } else {
// K -= cnt[u];
// }
// }
// string ans = "";
// ans += idx_to_char(curr);
// long long current_len = L_max;
// // Pas 4: Avansăm nod cu nod pentru a construi drumul
// while (current_len > 0) {
// for (int v : adj[curr]) {
// // Ne interesează doar vecinii care mențin lungimea maximă rămasă
// if (max_len[v] == current_len - 1) {
// if (K <= cnt[v]) {
// curr = v;
// ans += idx_to_char(curr);
// current_len--;
// break; // Am găsit următorul nod, reluăm procesul din el
// } else {
// K -= cnt[v];
// }
// }
// }
// }
// fout << ans << "\n";
// return 0;
// }
// //-------------------------------------------------------------
// Freakadebunic
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <algorithm>
// using namespace std;
// const int MAXN = 100005;
// vector<int> adj[MAXN];
// bool are_trupa[MAXN];
// int parinte[MAXN];
// int nr_trupe_subarbore[MAXN];
// bool vizitat[MAXN];
// int main() {
// ifstream fin("freakadebunic.in");
// ofstream fout("freakadebunic.out");
// int N, K;
// if (!(fin >> N >> K)) return 0;
// for (int i = 0; i < K; ++i) {
// int x;
// fin >> x;
// are_trupa[x] = true;
// }
// for (int i = 0; i < N - 1; ++i) {
// int u, v;
// fin >> u >> v;
// adj[u].push_back(v);
// adj[v].push_back(u);
// }
// // 1. Parcurgere BFS pentru a ordona nodurile de sus în jos (fără recursivitate!)
// vector<int> ordine;
// ordine.reserve(N);
// ordine.push_back(1);
// vizitat[1] = true;
// for (int i = 0; i < (int)ordine.size(); ++i) {
// int u = ordine[i];
// for (int v : adj[u]) {
// if (!vizitat[v]) {
// vizitat[v] = true;
// parinte[v] = u;
// ordine.push_back(v);
// }
// }
// }
// vector<int> devreme;
// // 2. Parcurgem nodurile invers (de la frunze spre rădăcină)
// for (int i = N - 1; i >= 0; --i) {
// int u = ordine[i];
// int surse = 0;
// // Dacă e o trupă chiar în nodul u, e o primă sursă
// if (are_trupa[u]) {
// surse++;
// nr_trupe_subarbore[u]++;
// }
// // Verificăm fiii lui u
// for (int v : adj[u]) {
// if (v != parinte[u]) {
// if (nr_trupe_subarbore[v] > 0) {
// surse++; // Acest fiu aduce cel puțin o trupă din subarborele său
// nr_trupe_subarbore[u] += nr_trupe_subarbore[v];
// }
// }
// }
// // Dacă se întâlnesc trupe din cel puțin 2 direcții/surse, u este nod "devreme"
// if (surse >= 2) {
// devreme.push_back(u);
// }
// }
// // Sortăm crescător nodurile găsite
// sort(devreme.begin(), devreme.end());
// // Afișare
// fout << devreme.size() << "\n";
// for (int u : devreme) {
// fout << u << " ";
// }
// fout << "\n";
// return 0;
// }
// //-------------------------------------------------------------
// // pamant
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <algorithm>
// using namespace std;
// const int MAXN = 100005;
// vector<int> adj[MAXN];
// int tin[MAXN], low[MAXN];
// int timer = 0;
// bool vizitat[MAXN];
// bool este_vulnerabil[MAXN];
// vector<int> coduri_echipe;
// vector<int> copii_vulnerabili;
// int minim_echipa_curenta;
// // Parcurgerea DFS care calculează și componentele conexe și punctele de articulație
// void dfs(int u, int p = -1) {
// vizitat[u] = true;
// tin[u] = low[u] = ++timer;
// // Actualizăm codul (nodul minim) pentru echipa curentă
// minim_echipa_curenta = min(minim_echipa_curenta, u);
// int numar_fii_dfs = 0;
// for (int v : adj[u]) {
// if (v == p) continue; // Nu ne întoarcem pe muchia din care abia am venit
// if (vizitat[v]) {
// // Am dat de o muchie de întoarcere
// low[u] = min(low[u], tin[v]);
// } else {
// // Este un fiu nou în arborele DFS
// numar_fii_dfs++;
// dfs(v, u);
// // Când ne întoarcem din fiu, actualizăm valoarea low a părintelui
// low[u] = min(low[u], low[v]);
// // Verificăm condiția de punct de articulație pentru un nod care NU e rădăcină
// if (p != -1 && low[v] >= tin[u]) {
// este_vulnerabil[u] = true;
// }
// }
// }
// // Condiția de punct de articulație pentru rădăcina arborelui DFS
// if (p == -1 && numar_fii_dfs > 1) {
// este_vulnerabil[u] = true;
// }
// }
// int main() {
// ifstream fin("pamant.in");
// ofstream fout("pamant.out");
// int n, m;
// if (!(fin >> n >> m)) return 0;
// for (int i = 0; i < m; ++i) {
// int u, v;
// fin >> u >> v;
// adj[u].push_back(v);
// adj[v].push_back(u);
// }
// // Identificăm componentele conexe (Echipele)
// for (int i = 1; i <= n; ++i) {
// if (!vizitat[i]) {
// minim_echipa_curenta = i; // Inițializăm cu nodul de start
// dfs(i, -1);
// coduri_echipe.push_back(minim_echipa_curenta);
// }
// }
// // Colectăm copiii vulnerabili găsiți de DFS
// for (int i = 1; i <= n; ++i) {
// if (este_vulnerabil[i]) {
// copii_vulnerabili.push_back(i);
// }
// }
// // Sortăm listele pentru afișarea cerută în enunț
// sort(coduri_echipe.begin(), coduri_echipe.end());
// // (copii_vulnerabili sunt deja în ordine crescătoare, dar e o practică bună)
// sort(copii_vulnerabili.begin(), copii_vulnerabili.end());
// // Afișăm cele 4 linii de output
// fout << coduri_echipe.size() << "\n";
// for (int cod : coduri_echipe) {
// fout << cod << " ";
// }
// fout << "\n";
// fout << copii_vulnerabili.size() << "\n";
// for (int copil : copii_vulnerabili) {
// fout << copil << " ";
// }
// fout << "\n";
// return 0;
// }
// //-------------------------------------------------------------
// // Componente biconexe
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <stack>
// #include <algorithm>
// using namespace std;
// const int MAXN = 100005;
// vector<int> adj[MAXN];
// int tin[MAXN], low[MAXN];
// int timer = 0;
// stack<int> st;
// // Reținem componentele într-un vector de vectori pentru a le număra ușor la final
// vector<vector<int>> bccs;
// void dfs(int u, int p = -1) {
// tin[u] = low[u] = ++timer;
// st.push(u); // Punem nodul curent în stivă
// for (int v : adj[u]) {
// if (v == p) continue; // Ignorăm muchia de întoarcere la părintele direct
// if (tin[v]) { // Nod deja vizitat -> muchie de întoarcere (back edge)
// low[u] = min(low[u], tin[v]);
// } else { // Nod nevizitat -> avansăm în DFS
// dfs(v, u);
// low[u] = min(low[u], low[v]);
// // Verificăm condiția de punct de articulație
// if (low[v] >= tin[u]) {
// vector<int> current_bcc;
// int extras;
// // Scoatem din stivă tot subarborele lui v care a rămas izolat
// do {
// extras = st.top();
// st.pop();
// current_bcc.push_back(extras);
// } while (extras != v);
// // Adăugăm și nodul u (punctul de articulație) în componentă,
// // dar FĂRĂ a-l scoate definitiv din stiva globală!
// current_bcc.push_back(u);
// bccs.push_back(current_bcc);
// }
// }
// }
// }
// int main() {
// ifstream fin("biconex.in");
// ofstream fout("biconex.out");
// int N, M;
// if (!(fin >> N >> M)) return 0;
// for (int i = 0; i < M; ++i) {
// int u, v;
// fin >> u >> v;
// adj[u].push_back(v);
// adj[v].push_back(u);
// }
// // Graful poate fi neconex, deci pornim DFS din fiecare componentă conexă izolată
// for (int i = 1; i <= N; ++i) {
// if (!tin[i]) {
// dfs(i);
// }
// }
// // Afișăm rezultatele
// fout << bccs.size() << "\n";
// for (const auto& comp : bccs) {
// for (int nod : comp) {
// fout << nod << " ";
// }
// fout << "\n";
// }
// return 0;
// }
// //-------------------------------------------------------------
// // Componente biconexe
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
vector<int> adj[MAXN];
int tin[MAXN], low[MAXN];
bool in_stack[MAXN];
int timer = 0;
stack<int> st;
vector<vector<int>> ctc;
void dfs(int u) {
tin[u] = low[u] = ++timer;
st.push(u);
in_stack[u] = true;
for (int v : adj[u]) {
if (!tin[v]) {
// Nod nevizitat
dfs(v);
low[u] = min(low[u], low[v]);
} else if (in_stack[v]) {
// Nod vizitat și aflat în stivă (muchie de întoarcere validă)
low[u] = min(low[u], tin[v]);
}
// Dacă e vizitat dar NU e în stivă (cross-edge), îl ignorăm complet.
}
// Am terminat de explorat vecinii. Verificăm dacă u este rădăcina unei CTC.
if (low[u] == tin[u]) {
vector<int> componenta_curenta;
int extras;
// Extragem din stivă până dăm de u
do {
extras = st.top();
st.pop();
in_stack[extras] = false; // Îl marcăm ca scos
componenta_curenta.push_back(extras);
} while (extras != u);
ctc.push_back(componenta_curenta);
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
if (!(fin >> N >> M)) return 0;
for (int i = 0; i < M; ++i) {
int u, v;
fin >> u >> v;
adj[u].push_back(v); // Graf orientat, deci adăugăm doar u -> v
}
// Graful poate fi format din mai multe bucăți disjuncte
for (int i = 1; i <= N; ++i) {
if (!tin[i]) {
dfs(i);
}
}
// Afișarea rezultatelor
fout << ctc.size() << "\n";
for (const auto& comp : ctc) {
for (int nod : comp) {
fout << nod << " ";
}
fout << "\n";
}
return 0;
}
Manolescu Teodor teoo.mnl