Pagini recente » Clasament FMI No Stress 3 | Concursuri | Cod sursa (job #1302589) | Cod sursa (job #3216038) | Cod sursa (job #2925944)
#include <fstream>
#include <iostream>
#include <bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
vector < vector <int>> l(N);
vector <int> stkItem(N);
vector <int> disc(N) , lowLink(N);
stack <int> stk;
vector < vector <int>> sol(N);
int n, m, i, j, x, y, ct;
int t;
void Input(){
cin >> n >> m;
for(i=1; i<=m; i++)
{
cin >> x >> y;
l[x].push_back(y);
}
}
void findComponent(int node){
stk.push(node);
stkItem[node] = 1;
disc[node] = lowLink[node] = ++t;
for( i = 0; i < l[node].size(); i++){
int v = l[node][i];
if(disc[v] == 0)
findComponent(v);
if(stkItem[v])
lowLink[node] = min (lowLink[node], lowLink[v]);
}
int poppedItem = 0;
if(lowLink[node] == disc[node]){
while(stk.top() != node) {
poppedItem = stk.top();
stkItem[poppedItem] = 0;
lowLink[poppedItem] = disc[node];
stk.pop();
}
poppedItem = stk.top();
stkItem[poppedItem] = 0;
lowLink[poppedItem] = disc[node];
stk.pop();
ct ++;
}
}
void SCC(){
for(i = 1; i <= n; i++)
if(disc[i] == 0)
findComponent(i);
for(i = 1; i <= n; i++)
{
sol[lowLink[i]].push_back(i);
}
cout << ct <<"\n";
for(i = 1; i <= n; i++) {
if(sol[i].size())
{
for(j = 0; j < sol[i].size(); j++)
cout << sol[i][j] <<" ";
}
cout <<"\n";
}
}
int main()
{
Input();
SCC();
return 0;
}