Pagini recente » Profil bolnot | Profil NekroDana | Rating Barbulescu Robert-Cristian (Robert2407) | Cod sursa (job #2126154) | Cod sursa (job #937492)
Cod sursa(job #937492)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int> > adjl;
vector<int> index, lowlink;
stack<int> s;
vector<vector<int> > scc;
int mins(0), cur(0);
void strongconnect(int i)
{
index[i] = lowlink[i] = ++cur;
s.push(i);
int v;
for (vector<int>::iterator it = adjl[i].begin(); it != adjl[i].end(); ++it) {
v = *it;
if (index[v] == 0) strongconnect(v);
if (index[v] > mins && lowlink[i] > lowlink[v]) lowlink[i] = lowlink[v];
}
if (index[i] == lowlink[i]) {
scc.push_back(vector<int>());
do {
v = s.top();
s.pop();
scc.back().push_back(v);
} while (v != i);
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
adjl.resize(n+1);
index.resize(n+1);
lowlink.resize(n+1);
int u, v;
for (; m > 0; --m) {
fin >> u >> v;
adjl[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (index[i] == 0) {
mins = cur;
strongconnect(i);
}
}
fout << scc.size() << '\n';
for (int i = scc.size()-1; i >= 0; --i) {
for (int j = scc[i].size()-1; j >= 0; --j)
fout << scc[i][j] << ' ';
fout << '\n';
}
return 0;
}