Pagini recente » Cod sursa (job #2032933) | Cod sursa (job #949548) | Cod sursa (job #2456265) | Cod sursa (job #1724960) | Cod sursa (job #2302175)
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
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 T(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)
T(*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)
T(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";
}
}