Pagini recente » Cod sursa (job #2493666) | Cod sursa (job #1584465) | Cod sursa (job #1917569) | Cod sursa (job #1934077) | Cod sursa (job #905133)
Cod sursa(job #905133)
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <stack>
using namespace std;
#define MAXN 100005
#define min(a, b) ((a) < (b) ? (a) : (b))
vector <int> adj[MAXN], idx, lowlink, stiva, comp;
vector < vector <int> > sol;
stack <int> s;
int index;
ifstream in("ctc.in");
ofstream out("ctc.out");
void read (vector <int> *adj, int &n)
{
int m, x, y;
in >> n;
for (in >> m; m > 0; -- m)
{
in >> x >> y;
x --, y --;
adj[x].push_back(y);
}
}
void print(const vector < vector <int> > &G)
{
out << G.size() << "\n";
for(size_t i = 0; i < G.size(); ++ i)
{
for(size_t j = 0; j < G[i].size(); ++ j)
out << G[i][j] + 1 << " ";
out << "\n";
}
}
void tarjan (const int n, const vector <int> *adj)
{
idx[n] = lowlink[n] = index;
index++;
s.push(n);
stiva[n] = 1;
vector <int>::const_iterator it;
for( it = adj[n].begin(); it != adj[n].end(); ++it)
{
if(idx[*it] == -1)
{
tarjan(*it, adj);
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
else
if(stiva[*it])
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
if(idx[n] == lowlink[n])
{
comp.clear();
int nod;
do{
nod = s.top();
comp.push_back(nod);
s.pop();
stiva[nod] = 0;
}
while (nod != n);
sol.push_back(comp);
}
}
int main()
{
int n;
read(adj, n);
idx.resize(n); idx.assign(n, -1);
stiva.resize(n); stiva.assign(n, 0);
lowlink.resize(n);
for(int i = 0; i < n; ++ i)
if(idx[i] == -1)
tarjan(i, adj);
print(sol);
return 0;
}