Pagini recente » Cod sursa (job #1801231) | Istoria paginii utilizator/usordememorat | Cod sursa (job #355703) | Cod sursa (job #2493891) | Cod sursa (job #1601678)
#include <fstream>
#include <vector>
#include <stack>
#include <list>
#define f first
#define s second
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, i, reach, nrComp;
bool onStack[100100];
vector<pair<int, int> > nodeOrders(100100);
vector<list<int> > graph(100100);
list<list<int> > solution;
list<int> xList;
stack<int> strongConnect;
void tareConex(int nod) {
int aux;
if (nodeOrders[nod].f == 0) {
reach++;
nodeOrders[nod].f = reach;
nodeOrders[nod].s = reach;
onStack[nod] = true;
strongConnect.push(nod);
for (list<int>::iterator it = graph[nod].begin() ; it != graph[nod].end() ; it++) {
if (nodeOrders[*it].f == 0) {
tareConex(*it);
nodeOrders[nod].s = min(nodeOrders[nod].s, nodeOrders[*it].s);
} else if (onStack[*it] == true) {
nodeOrders[nod].s = min(nodeOrders[nod].s, nodeOrders[*it].s);
}
}
if (nodeOrders[nod].f == nodeOrders[nod].s) {
do {
aux = strongConnect.top(); strongConnect.pop();
onStack[aux] = false;
xList.push_back(aux);
} while (aux != nod);
solution.push_back(xList);
xList.clear();
nrComp++;
}
}
}
int main()
{
fin>>n>>m;
for (i = 1 ; i <= m ; i++) {
fin>>x>>y;
graph[x].push_back(y);
}
for (i = 1 ; i <= n ; i++) {
tareConex(i);
}
fout<<nrComp;
for (list<list<int> >::iterator listIt = solution.begin() ; listIt != solution.end() ; listIt++) {
fout<<'\n';
for (list<int>::iterator it = listIt->begin() ; it != listIt->end() ; it++) {
fout<<*it<<' ';
}
}
return 0;
}