Pagini recente » Cod sursa (job #1865971) | Cod sursa (job #2985938) | Cod sursa (job #686262) | Cod sursa (job #1188650) | Cod sursa (job #1213372)
#include <fstream>
#include <vector>
#include <stack>
#define DIMN 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> L[DIMN], Rez[DIMN];
int Niv[DIMN], Low[DIMN];
int m, n, ctc = 0, nivel = 0, x, y;
stack<int> s;
void DFS (int nod) {
Niv[nod] = Low[nod] = ++nivel;
s.push(nod);
for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); ++it) {
if (Niv[*it] == 0)
DFS (*it);
if (Niv[*it] > 0)
Low[nod] = min(Low[nod], Low[*it]);
}
if (Niv[nod] == Low[nod]) {
++ctc;
while (s.top() != nod) {
Rez[ctc].push_back(s.top());
Niv[s.top()] *= -1;
s.pop();
}
Rez[ctc].push_back(s.top());
Niv[s.top()] *= -1;
s.pop();
}
}
int main () {
f >> n >> m;
for (int i=1; i<=m; ++i) {
f >> x >> y;
L[x].push_back(y);
}
for (int i=1; i<=n; ++i)
if (Niv[i] == 0)
DFS (i);
g << ctc << "\n";
for (int i=1; i<=ctc; ++i) {
for (vector<int>::iterator it=Rez[i].begin(); it!=Rez[i].end(); ++it)
g << *it << " ";
g << "\n";
}
return 0;
}