Pagini recente » Cod sursa (job #1782230) | Cod sursa (job #1442433) | Cod sursa (job #1388544) | Cod sursa (job #9599) | Cod sursa (job #2198032)
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int kNmax = 100005, ALB = 0, GRI = 1, NEGRU = 2;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<int> adj[kNmax];
vector<int> adjt[kNmax];
stack<int> s;
vector<int> cul;
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);
adjt[y].push_back(x);
}
fin.close();
}
void dfs(int nod) {
cul[nod] = GRI;
for(unsigned i = 0; i < adj[nod].size(); ++i)
if(cul[ adj[nod][i] ] == ALB)
dfs(adj[nod][i]);
s.push(nod);
cul[nod] = NEGRU;
}
void dfst(int nod, vector<int> &com) {
cul[nod] = GRI;
com.push_back(nod);
for(unsigned i = 0; i < adjt[nod].size(); ++i)
if(cul[ adjt[nod][i] ] == ALB)
dfst(adjt[nod][i], com);
cul[nod] = NEGRU;
}
void ctc(vector<vector<int> > &sol) {
cul.resize(n + 1);
for(int i = 1; i <= n; ++i)
cul[i] = ALB;
while(!s.empty()) {
s.pop();
}
for(int i = 1; i <= n; ++i) {
if(cul[i] == ALB)
dfs(i);
}
for(int i = 1; i <= n; ++i)
cul[i] = ALB;
while(!s.empty()) {
int nod = s.top();
s.pop();
if(cul[nod] == ALB) {
vector<int> com;
dfst(nod, com);
sol.push_back(com);
}
}
}
vector<vector<int>> get_result() {
/*
TODO: Gasiti componentele tare conexe ale grafului orientat cu
n noduri, stocat in adj. Rezultatul se va returna sub forma
unui vector, ale carui elemente sunt componentele tare conexe
detectate. Nodurile si componentele tare conexe pot fi puse in orice
ordine in vector.
Atentie: graful transpus este stocat in adjt.
*/
vector<vector<int>> sol;
ctc(sol);
return sol;
}
void print_output(vector<vector<int>> result) {
ofstream fout("ctc.out");
fout << result.size() << '\n';
for (const auto& ctc : result) {
for (int nod : ctc) {
fout << nod << ' ';
}
fout << '\n';
}
fout.close();
}
};
int main() {
Task *task = new Task();
task->solve();
delete task;
return 0;
}