Pagini recente » Cod sursa (job #2877202) | Cod sursa (job #1813838) | Cod sursa (job #1998852) | Cod sursa (job #972011) | Cod sursa (job #1934559)
//#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <stack>
#define nmax 100999
using namespace std;
list<int> g[nmax];
list<int> com[nmax];
vector<bool> proceded(nmax,false);
int timp,dfn[nmax],t[nmax],n,low[nmax],comp[nmax],nrc;
stack<int > st;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void afisare(int x)
{int t;nrc++;
do{
t=st.top();
comp[t]=nrc;
st.pop();
// cout<<t<<' ';
}while(t!=x);
// cout<<endl;
}
void citire(){
int m,x,y;
fin>>n>>m;
while(m--)
{
fin>>x>>y;
g[x].push_back(y);
}
}
void dfs(int x)
{
dfn[x]=++timp;
int y;
for(list<int>::iterator it=g[x].begin(); it!=g[x].end(); it++)
{y=*it;
//st.push(y);
if(!dfn[y])
{ //Tree edge:
st.push(y);
t[y]=x;
dfs(y);
}
else if(dfn[y]<dfn[x] && !proceded[y]){
//Back-edges:
if(dfn[y] < dfn[ low[x] ])
low[x]=y;
}
else if(dfn[y]<dfn[x] && proceded[y]){
//Cross-edge:
if(!comp[y])
if(dfn[y] < dfn[low[x]])
low[x]=y;
}
}
if( low[x] ==x )
afisare(x);
if( dfn[ low[t[x]] ] > dfn[low[x]])
low[t[x]]=low[x];
proceded[x]=1;
}
int main()
{
citire();
int i;
for(i=1;i<=n;i++)low[i]=i;
for(i=1;i<=n;i++)
{st.push(i);
if(!dfn[i])dfs(i);}
for(i=1;i<=n;i++)
com[comp[i]].push_back(i);
fout<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{for(list<int>::iterator it=com[i].begin();it!=com[i].end();it++)
fout<<*it<<' ';
fout<<'\n';}
}