Pagini recente » Cod sursa (job #2174279) | Cod sursa (job #1114345) | Cod sursa (job #1820872) | Cod sursa (job #2707031) | Cod sursa (job #1361949)
#include <fstream>
#include <iostream>
#include <vector>
#define MAXN 100001
using namespace std;
int n, m, ni, nr;
bool p[MAXN], viz[MAXN], vizt[MAXN];
vector<int> v[MAXN], vt[MAXN], s[MAXN];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void DFS (int nc) {
vector<int>::iterator i;
viz[nc] = true;
for (i = v[nc].begin(); i != v[nc].end(); ++i)
if (not viz[*i])
DFS (*i);
}
void DFSt (int nc) {
vector<int>::iterator i;
vizt[nc] = true;
for (i = vt[nc].begin(); i != vt[nc].end(); ++i)
if (not vizt[*i])
DFSt (*i);
}
int main() {
int i, j, l, c;
fin >> n >> m; // Se citeste numarul de noduri si numarul de muchii.
for (i = 1; i <= m; i++) { // Pentru fiecare muchie
fin >> l >> c; // Se citesc informatiile despre o muchie.
v[l].push_back(c);
vt[c].push_back(l); // vecini in graful transpus
}
for (i = 1; i <= n; i++)
p[i] = true;
for (i = 1; i <= n; i++)
if (p[i]) {
nr++;
DFS(i);
DFSt(i);
for (j = 1; j <= n; j++)
if (viz[j] and vizt[j]) {
s[nr].push_back(j); p[j] = false;
}
for (j = 1; j <= n; j++)
viz[j] = vizt[j] = 0;
}
fout << nr << '\n';
for (c = 1; c <= nr; c++) { // c - componenta
for (n = 0; n <= s[c].size() - 1; n++) // n - nodul
fout << s[c][n] << ' ';
fout << '\n';
}
return 0;
}