Pagini recente » Cod sursa (job #1458841) | Cod sursa (job #1098616) | Cod sursa (job #866680) | Cod sursa (job #2492435) | Cod sursa (job #766162)
Cod sursa(job #766162)
#include <stdio.h>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100001
using namespace std;
int n, m, ind = 1;
stack<int> S;
vector< vector<int> > rez;
vector<int> edges[NMAX];
int lowlink[NMAX];
int index[NMAX];
bool inStack[NMAX];
int min(int a, int b) {
return a < b ? a : b;
}
void read_() {
int source, dest;
ifstream fin("ctc.in");
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> source >> dest;
edges[source].push_back(dest);
}
fin.close();
}
void vertex_init(int poz) {
index[poz] = ind;
lowlink[poz] = ind;
ind++;
inStack[poz] = true;
S.push(poz);
}
void dfs_tarj(int poz) {
vertex_init(poz);
vector<int>::iterator it;
for (it = edges[poz].begin(); it != edges[poz].end(); it++) {
if (index[*it] == 0) {
dfs_tarj(*it);
lowlink[poz] = min(lowlink[poz], lowlink[*it]);
} else if (inStack[*it] == true) {
lowlink[poz] = min(lowlink[poz], index[*it]);
}
}
if (lowlink[poz] == index[poz]) {
vector<int> ctc;
inStack[S.top()] = false;
ctc.push_back(S.top());
while (S.top() != poz) {
S.pop();
inStack[S.top()] = false;
ctc.push_back(S.top());
}
S.pop();
rez.push_back(ctc);
}
}
void tarjan() {
for (int i = 1; i <= n; i++) {
if (index[i] == 0) {
dfs_tarj(i);
}
}
}
void write_() {
freopen("ctc.out", "w", stdout);
vector< vector<int> >::iterator set_it;
vector<int>::iterator vect_it;
printf("%d \n", rez.size());
for (set_it = rez.begin(); set_it != rez.end(); set_it++) {
vector<int> ctc = *set_it;
for (vect_it = ctc.begin(); vect_it != ctc.end(); vect_it++) {
printf("%d ", *vect_it);
}
printf("\n");
}
}
int main() {
read_();
tarjan();
write_();
return 0;
}