Pagini recente » Cod sursa (job #1737484) | Cod sursa (job #1991164) | Cod sursa (job #671184) | Cod sursa (job #383598) | Cod sursa (job #2302170)
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
#define Min(a, b) ((a) < (b) ? (a) : (b))
vector<int> adj[N],con,idx,lowlink,in_stack;
vector<vector<int>> C;
stack<int> S;
int indecs,n,i,j,x,y,cnt_edges;
void tarjan(const int n, const vector <int>* adj)
{
idx[n] = lowlink[n] = indecs;
indecs ++;
S.push(n), in_stack[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 (in_stack[*it])
lowlink[n] = Min(lowlink[n], lowlink[*it]);
if (idx[n] == lowlink[n])
{
con.clear();
int node;
do {
con.push_back(node = S.top());
S.pop(), in_stack[node] = 0;
}
while (node != n);
C.push_back(con);
}
}
int main(void)
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n;
for(f>>cnt_edges;cnt_edges>0;cnt_edges--)
f>>x>>y,adj[x-1].push_back(y-1);
idx.resize(n),lowlink.resize(n),in_stack.resize(n),idx.assign(n,-1),in_stack.assign(n,0);
for(i=0;i<n;i++)
if(idx[i]==-1)
tarjan(i,adj);
g<<C.size()<<"\n";
for(i=0;i<C.size();i++)
{
for(j=0;j<C[i].size();j++)
g<<C[i][j]+1<<" ";
g<<"\n";
}
}