Pagini recente » Cod sursa (job #1697907) | Cod sursa (job #1264316) | Cod sursa (job #949665) | Istoria paginii runda/4/clasament | Cod sursa (job #2945035)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nrctc;
vector<int> adi[100001];
vector<int> adit[100001]; //graful transpus
stack<int> s;
vector<vector<int>> sol; //solutia problemei
bool viz[100001];
void citire() {
cout << "u";
int a, b;
fin >> N >> M;
for(int i = 1; i <= M; i++) {
fin >> a >> b;
adi[a].push_back(b);
adit[b].push_back(a);
}
}
void dfs(int nod) {
for(int u : adi[nod]) {
if(!viz[u]) {
viz[u] = true;
dfs(u);
}
}
s.push(nod);
cout << nod << " ";
}
void faza1() {
//in faza 1 vom face cate un dfs din noduri arbitrare (toate acelea nevizitate)
for(int start = 1; start <= N; start++) {
if(!viz[start]) {
viz[start] = true;
dfs(start);
}
}
}
void dfs2(int nod) {
for(int u : adit[nod]) {
if(!viz[u]) {
viz[u] = true;
sol[nrctc - 1].push_back(u);
dfs2(u);
}
}
}
void faza2() {
//in faza 2 vom lua nodurile din stiva si facand dfs pe acelea vom gasi componentele tari conexe
for(int i = 1; i <= N; i++) {
viz[i] = false;
}
while(!s.empty()) {
int start = s.top();
s.pop();
if(!viz[start]) {
nrctc++;
sol.push_back({});
sol[nrctc - 1].push_back(start);
viz[start] = true;
dfs2(start);
}
}
}
void afisare() {
fout << nrctc << "\n";
for(int i = 0; i < nrctc; i++) {
for(int u : sol[i]) {
fout << u << " ";
}
fout << "\n";
}
}
int main() {
citire();
faza1();
faza2();
afisare();
return 0;
}