Pagini recente » Cod sursa (job #3157835) | Cod sursa (job #737428) | Cod sursa (job #2094383) | Cod sursa (job #604674) | Cod sursa (job #1004455)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct node {
bool vizitat;
int mini;
int grad;
vector<int> vecini;
};
struct cuplu {
int a;
int b;
};
int n, m, i, ii, a, b, s1, s2, k = 1;
node nodes[100001];
stack<int> stiva;
vector<int> sol;
vector<vector<int> > solutie;
bool v[100001];
void dfs(int x) {
int j;
int l = nodes[x].vecini.size();
for(j = 0; j < l; j++) {
int vecin = nodes[x].vecini[j];
//cout << "nod: " << x << '(' << nodes[x].mini << ')' << "-vecin: " << vecin << '(' << nodes[vecin].mini << ")\n";
if(nodes[vecin].vizitat == false) {
stiva.push(vecin);
v[vecin] = true;
nodes[vecin].vizitat = true;
nodes[vecin].grad = nodes[vecin].mini = ++k;
dfs(vecin);
nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
//cout << "nod: "<< x << '(' << nodes[x].mini << ")-vecin: " << vecin << '(' << nodes[vecin].mini << ")\n";
}
else {
if(v[vecin] == true) {
nodes[x].mini = min(nodes[x].mini, nodes[vecin].mini);
//cout << "nod': " << x << '(' << nodes[x].mini << ")\n";
}
}
}
if(nodes[x].grad == nodes[x].mini) {
while(stiva.top() != x) {
sol.push_back(stiva.top());
v[stiva.top()] = false;
stiva.pop();
}
sol.push_back(stiva.top());
v[stiva.top()] = false;
stiva.pop();
solutie.push_back(sol);
sol.clear();
}
}
int main() {
fin >> n >> m;
for(i = 0; i < m; i++) {
fin >> a >> b;
nodes[a].vecini.push_back(b);
}
for(i = 1; i <= n; i++) {
if(nodes[i].vizitat == false) {
nodes[i].grad = k;
nodes[i].mini = k;
stiva.push(i);
v[i] = true;
nodes[i].vizitat = true;
dfs(i);
}
}
s1 = solutie.size();
fout << s1 << '\n';
for(i = s1 - 1; i >= 0; i--) {
sol = solutie[i];
s2 = sol.size();
for(ii = s2 - 1; ii >= 0; ii--) {
fout << sol[ii] << ' ';
}
fout << '\n';
}
fin.close();
fout.close();
return 0;
}