Pagini recente » Cod sursa (job #1852185) | Cod sursa (job #2643994) | Cod sursa (job #889516) | Cod sursa (job #1917478) | Cod sursa (job #2969177)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int dim = 1e5 + 5;
int n,m, viz[dim], distante[dim], s, in_deg[dim];
vector<int> vec_nocost[dim];
vector<int> vec_nocost_transpus[dim];
vector<int> vizitate_acum;
stack<int> st;
void Citeste_nocost() {
in >> n >> m;
// in >> s;
for (int i=0, x, y; i<m; i++) {
in >> x >> y;
in_deg[y]++;
vec_nocost[x].push_back(y);
// vec_nocost[y].push_back(x);
vec_nocost_transpus[y].push_back(x);
}
}
void DFS(int nod) {
viz[nod] = 1;
for (auto y:vec_nocost[nod]) {
if (!viz[y]) {
DFS(y);
}
}
st.push(nod);
}
void DFS_transpus(int nod) {
viz[nod] = 1;
vizitate_acum.push_back(nod);
for (auto y:vec_nocost_transpus[nod]) {
if (!viz[y]) {
DFS_transpus(y);
}
}
}
void BFS(int start) {
for (int i=1; i<=n; i++) {
distante[i] = -1;
}
distante[start] = 0;
queue<int> q;
q.push(start);
viz[start] = 1;
while (!q.empty()) {
int nod = q.front();
q.pop();
for (auto y:vec_nocost[nod]) {
if (!viz[y]) {
viz[y] = 1;
distante[y] = distante[nod] + 1;
q.push(y);
}
}
}
for (int i=1; i<=n; i++) {
out << distante[i] << " ";
}
}
int Nr_CompConexe() {
int cnt = 0;
for (int i=1; i<=n; i++) {
if (!viz[i]) {
cnt++;
DFS(i);
}
}
return cnt;
}
vector<int> SortareTopologicaBFS() {
queue<int> q;
vector<int> rasp;
for (int i=1; i<=n; i++) {
if (in_deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int nod = q.front();
q.pop();
rasp.push_back(nod);
for (auto y:vec_nocost[nod]) {
in_deg[y]--;
if (in_deg[y] == 0) {
q.push(y);
}
}
}
return rasp;
}
void AfisVector(vector<int> &vec) {
for (auto y:vec) {
out << y << " ";
}
}
void ComponenteTareConexe() {
for (int i=1; i<=n; i++) {
if (!viz[i]) {
DFS(i);
}
}
for (int i=1; i<=n; i++) {
viz[i] = 0;
}
vector<vector<int>> vec;
while (!st.empty()) {
int nod = st.top();
st.pop();
if (!viz[nod]) {
vizitate_acum.clear();
DFS_transpus(nod);
vec.push_back(vizitate_acum);
}
}
out << vec.size() << "\n";
for (int i=0; i<vec.size(); i++) {
for (auto y:vec[i]) {
out << y << " ";
}
out << "\n";
}
}
int main() {
Citeste_nocost();
/* vector<int> rasp = SortareTopologicaBFS();
AfisVector(rasp);*/
// /// sortare topologica cu DFS
// for (int i=1; i<=n; i++) {
// if (!viz[i] && in_deg[i] == 0) {
// DFS(i);
// }
// }
// while (!st.empty()) {
// out << st.top() << " ";
// st.pop();
// }
ComponenteTareConexe();
return 0;
}