Pagini recente » Cod sursa (job #1906749) | Cod sursa (job #2023326) | Cod sursa (job #2116980) | Cod sursa (job #379540) | Cod sursa (job #632325)
Cod sursa(job #632325)
#include<cstdio>
#include<vector>
#include<deque>
using namespace std;
int n,m,x,y,scc,i,T,index[100010],lowlink[100010],S[100010];
vector<int> SCC[100010],G[100010];
deque<int> Stack;
void read(),solve(),strongconnect(int);
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
}
}
void solve()
{
for(i=1;i<=n;i++)
{
if(!index[i])
strongconnect(i);
}
printf("%d\n",scc);
for(i=1;i<=scc;i++)
{
for(vector<int>::iterator it=SCC[i].begin();it!=SCC[i].end();it++)printf("%d ",*it);
printf("\n");
}
}
void strongconnect(int nod)
{
T++;
index[nod]=T;
lowlink[nod]=T;
Stack.push_back(nod);
S[nod]=1;
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
{
//daca nu e vizitat, vizitez fiul
if(!index[*it])
{
strongconnect(*it);
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}
//daca fiul e in stiva, actualizez lowlink
else if(S[*it])
lowlink[nod]=min(lowlink[nod],index[*it]);
}
if(index[nod]==lowlink[nod])
{
//introduc elementul in componenta tare conexa
int w=Stack.back();
SCC[++scc].push_back(w);
//scot nodul din stiva
Stack.pop_back();
S[w]=0;
while(nod!=w)
{
w=Stack.back();
Stack.pop_back();
S[w]=0;
SCC[scc].push_back(w);
}
}
}