Pagini recente » Cod sursa (job #3181240) | Cod sursa (job #551187) | Cod sursa (job #1710010) | Cod sursa (job #1558869) | Cod sursa (job #1240984)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 100000 + 1;
int n, m, indexCrt, nrcomp;
int index[NMAX], lowlink[NMAX];
bool instack[NMAX];
vector <int> v[NMAX];
vector <int> comp[NMAX];
stack <int> st;
void citeste() {
int a, b;
f >> n >> m;
for (int i = 1; i <= m; i++) {
f >> a >> b;
v[a].push_back(b);
}
}
void tarjan(int nod) {
index[nod] = indexCrt;
lowlink[nod] = indexCrt;
indexCrt++;
st.push(nod);
instack[nod] = 1;
int nod2, l = v[nod].size();
for (int i = 0; i < l; i++) {
nod2 = v[nod][i];
if (index[nod2] == 0) {
tarjan(nod2);
lowlink[nod] = min(lowlink[nod], lowlink[nod2]);
}
else if (instack[nod2]) {
lowlink[nod] = min(lowlink[nod], index[nod2]);
}
}
if (lowlink[nod] == index[nod]) {
nrcomp++;
//comp[nrcomp].push_back(nod);
while (nod2 != nod){
nod2 = st.top(); st.pop();
comp[nrcomp].push_back(nod2);
}
}
}
void scrie() {
int l;
g << nrcomp << '\n';
for (int i = 1; i <= nrcomp; i++) {
l = comp[i].size();
for (int j = 0; j < l; j++) g << comp[i][j] << ' ';
g << '\n';
}
}
int main() {
citeste();
for (int i = 1; i <= n; i++)
if (!index[i]) tarjan(i);
scrie();
return 0;
}