Pagini recente » Cod sursa (job #2096089) | Cod sursa (job #1764614) | Cod sursa (job #141176) | Cod sursa (job #21073) | Cod sursa (job #1179145)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int MAX_N = 100005;
const int MAX_M = 200005;
int n, m;
int idx[MAX_N]; // indicele in parcurgere
int lowlink[MAX_N]; // cat de sus pot sa ma duc
int index;
bool inStack[MAX_N];
vector <int> L[MAX_N];
vector <vector <int> > Ans;
stack <int> Stack;
void init() {
for (int i = 0; i < MAX_N; i++)
idx[i] = -1;
}
void read() {
f >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
f >> a >> b;
L[a].push_back (b);
}
}
void tarjan (int nod) {
index++;
idx[nod] = index;
lowlink[nod] = index;
Stack.push (nod);
inStack[nod] = true;
for (vector <int> :: iterator it = L[nod].begin(); it != L[nod].end(); ++it)
if (idx[*it] == -1) {
tarjan (*it);
lowlink[nod] = min (lowlink[nod], lowlink[*it]);
} else if (inStack[*it]) {
lowlink[nod] = min (lowlink[nod], idx[*it]);
}
// daca e radacina componentei tare conexe
if (lowlink[nod] == idx[nod]) {
vector <int> Temp;
int temp_node;
do {
temp_node = Stack.top();
Temp.push_back (temp_node);
Stack.pop();
inStack[temp_node] = false;
} while (temp_node != nod);
Ans.push_back (Temp);
}
}
void write() {
g << Ans.size() << '\n';
for (int i = 0; i < (int)Ans.size(); i++) {
for (vector <int> :: iterator it = Ans[i].begin(); it != Ans[i].end(); ++it)
g << *it << " ";
g << '\n';
}
}
int main() {
init();
read();
for (int i = 1; i <= n; i++)
if (idx[i] == -1)
tarjan (i);
write();
return 0;
}