Pagini recente » Cod sursa (job #491118) | Cod sursa (job #2188520) | Cod sursa (job #2021147) | Cod sursa (job #3195079) | Cod sursa (job #1999307)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 4e3 + 5;
int N,M,nrComp;
bool drum[NMax][NMax],inComp[NMax];
vector<int> v[NMax],comp[NMax];
// drum[i][j] - reprezinta initial daca exista arcul (i,j),
// ulterior inseamna ca exista drum de la i la j;
// inComp[i] = true daca s-a gasit deja componenta lui i;
// nrComp = numarul de componente gasite pana la momentul de fata;
// v[i] - lista de adiacenta a nodului i;
// comp[i] - nodurile ce fac parte din a i-a componenta tare conexa gasita;
int main() {
in>>N>>M;
while (M--) {
int x,y;
in>>x>>y;
drum[x][y] = true;
}
for (int i=1; i <= N;++i) {
drum[i][i] = true;
}
// se utilizeaza algoritmul Floyd - Roy - Warshall
// pentru a gasi daca exista drumuri intre oricare doua noduri
for (int k=1;k <= N;++k) {
for (int i=1;i <= N;++i) {
for (int j=1;j <= N;++j) {
if (drum[i][k] && drum[k][j]) {
drum[i][j] = true;
}
}
}
}
// doua noduri vor putea face parte din aceeasi componenta tare conexa
// doar daca exista drum de la i la j si drum de la j la i
for (int i=1;i <= N;++i) {
for (int j=1;j <= N;++j) {
if (drum[i][j] && drum[j][i]) {
continue;
}
drum[i][j] = 0;
drum[j][i] = 0;
}
}
// daca exista drumurile (i,j) si (j,k) vor exista si drumurile (i,k),(k,i)
// deci se poate arata usor ca daca n noduri
// sunt in aceeasi componenta tare conexa
// atunci fiecare nod va avea drum catre toate celelalte
for (int i=1;i <= N;++i) {
if (inComp[i]) {
continue;
}
// cautam nodurile spre care nodul i are drum si inapoi
++nrComp;
for (int j=1;j <= N;++j) {
if (drum[i][j]) {
comp[nrComp].pb(j);
inComp[j] = true;
}
}
}
out<<nrComp<<'\n';
for (int k=1;k <= nrComp;++k) {
for (auto node : comp[k]) {
out<<node<<' ';
}
out<<'\n';
}
in.close();
out.close();
return 0;
}